Optimization Online


The Windy Prize-Collecting Rural Postman Problem: An Ant-Colony Based Heuristic

S.E. Schaeffer (elisa.schaeffer***at***uanl.edu.mx)
R.Z. Rios-Mercado (roger***at***yalma.fime.uanl.mx)
E. Fernandez (e.fernandez***at***upc.edu)

Abstract: The Prize-collecting Rural Postman Problem, also known as the Privatized Rural Postman Problem, is an arc-routing problem where each demand edge is associated with a profit, which is collected once if the edge is served, independently of the number of traversals. Included edges incur in routing costs proportionally to the number of traversals. In this paper, we introduce the Windy Privatized Rural Postman Problem in which routing costs also depend on the direction of the traversals. For this problem, we propose a solution heuristic based on ant-colony optimization. The proposed method is capable of constructing profitable closed walks with low computational load.The quality of the obtained solutions can be assessed comparing their values to lower bounds.

Keywords: edge routing, price collecting, windy, ant-colony optimization

Category 1: Network Optimization

Citation: Withdrawn.


Entry Submitted: 04/14/2014
Entry Accepted: 05/01/2014
Entry Last Modified: 03/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society