The Periodic Capacitated Arc Routing Problem linear programming model, metaheuristic and lower bounds

Abstract

The Periodic Capacitated Arc Routing Problem (PCARP) generalizes the well known NP-hard Capacitated Arc Routing Problem (CARP) by extending the single period to multi-period horizon. The Capacitated Arc Routing Problem (CARP) is defined on an undirected network in which a fleet of identical vehicles is based at a depot node. A subset of edges, called tasks, must be serviced by a vehicle. The CARP consists of determining a set of feasible vehicle trips that minimizes the total cost of traversed edges. The PCARP involves the assignment of tasks to periods and the determination of vehicles trips in each period, to minimize the total cost on the whole horizon. This new problem arises in various real life applications such as waste collection, mail delivery, etc. In this paper, a new linear programming model and preliminary lower bounds based on graph transformation are proposed. A meta-heuristic approach-Scatter Search (SS) is developed for the PCARP and evaluated on a large variety of instances.

Keywords

PCARP / linear programming / lower bound / transformed graph / scatter search

References

[1] Amberg, A., Voß S., “A hierarchical relaxations lower bound for the capacitated arc routing problem”, IEEE-DTIST02 Proceedings of the 35th Annual Hawaii International Conference on System Sciences, Piscataway, pp1–10, 2002.

[2] Assad A., Pearn W.L., Golden B.L.. The capacitated Chinese postman problem: lower bounds and solvable cases. American Journal of Mathematical and Management Science, 1987, 7: 63-88.

[3] Belenguer J. M., Benavent E.. The capacitated are routing problem: valid inequalities and facets. Computational Optimization and Applications, 1998, 10: 165-187.

[4] Belenguer J. M., Benavent E.. A cutting plane algorithm for the capacitated arc routing problem. Computers and Operations Research, 2003, 30(5): 705-728.

[5] Benavent E., Campos V., Corberan A.. The capacitated arc routing problem: lower bounds. Networks, 1992, 22: 669-690.

[6] Benavent, E., Corberan A., Sanchis J.M., “Linear programming based methods for solving arc routing problems”, Arc Routing. Theory, Solutions and Applications, Kluwer Academic Publishers, pp231–275, 2000.

[7] Christofides N., Beasley J. E.. The period routing problem. Networks, 1994, 14: 237-256.

[8] Chu, F., Labadi N., Prins C., “Heuristics for the periodic capacitated arc routing problem”, To appear in Journal of Intelligent Manufacturing (JIM), 2004.

[9] Chu, F., Labadi N., Prins C., “A scatter search for the periodic capacitated arc routing problem”, To appear in European Journal of Operation Research (EJOR), 2004.

[10] Eglese R. W.. Routing winter gritting vehicles. Discrete Applied Mathematics, 1994, 48(3): 231-244.

[11] Eglese, R. W., Li L. Y. O., “A tabu search based heuristic for arc routing with a capacitated constraint and time deadline”, Metaheuristics: Theory and Applications, Kluwer, pp633–650, 1996.

[12] Glover F.. Heuristics for Integer programming using surrogate constraints. Decision Sciences, 1977, 8: 156-166.

[13] Golden B. L., Wong R. T.. Capacitated arc routing problems. Networks, 1981, 11: 305-315.

[14] Golden B. L.. Computational experiments with algorithms for a class of routing problems. Computers and Operation Research, 1983, 10(1): 47-59.

[15] Hertz A., Laporte G., Mittaz M.. A tabu search heuristic for the capacitated arc routing problem. Operations Research, 2000, 48(1): 129-135.

[16] Hirabayashi R., Saruwatari Y., Nishida N.. Tour construction algorithm for the capacitated arc routing problem. Asia-Pacific Journal of Operational Research, 1992, 9: 155-175.

[17] Kiuchi, M., Shinano Y. Hirabayashi R., Saruwatari Y., “An exact algorithm for the capacitated arc routing problem using parallel branch and bound method”, Abstracts of the Spring National Conference of the Oper. Res. Soc. of Japan, Japon, pp28–29, 1995.

[18] Lacomme, P., Prins, C., Ramdane-Chérif, W., “A genetic algorithm for the capacitated arc routing problem and its extensions”, Applications of Evolutionary Computing, LNCS 2037, Springer, pp473–483, 2001.

[19] Li L. Y. O.. Vehicle routing for winter gritting, 1992, United Kingdom: Lancaster University

[20] Pearn W. L.. New lower bounds for the capacitated arc routing problem. Networks, 1988, 18(3): 181-191.

[21] Ulusoy G.. The fleet size and mixed problem for capacitated arc routing problem. European Journal of Operational Research, 1985, 22(3): 329-337.

[22] Zaw W.. Contributions to routing problems, 1988, Germany: Universität Augsburg