Heuristics to Solve a Real-world Asymmetric Vehicle Routing Problem with Side Constraints

• Autorzy: Pham S. , Gascon V. , Dinh T.

Identyfikatory

DOI

10.3233/FI-2014-990

• Języki publikacji: EN

Abstrakty

EN

To maintain patients at home as most as possible, healthcare services are nowadays quite diversified. We present the case of a public medical clinic offering activities, mostly to the elderly, at a daycare center. Users are brought into the daycare center by bus or by taxi. The global problem consists in defining routes to pick up users while assigning them to time slots in the week. At first sight this problem could be viewed as an asymmetric multiple vehicle routing problem. However many additional constraints must be considered. In this paper, we propose a metaheuristic including two phases to solve the problem. In the first phase, the initial solution is determined using one of two proposed constructed algorithms and is improved using tabu search in the second phase. These algorithms are tested on 10 problem instances. Experimental results are presented.

Słowa kluczowe

EN

vehicle routing problem; sweep algorithm; saving heuristic; tabu search

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 2
• Strony: 231--246
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Pham S.

• Faculty of Information Technology, University of Science, Vietnam National University - Ho Chi Minh City, Vietnam

autor

Gascon V.

• Département des sciences de la gestion, Université du Québec à Trois-Rivières, Canada

autor

Dinh T.

• Faculty of Information Technology, University of Science, Vietnam National University - Ho Chi Minh City, Vietnam

Bibliografia

• [1] A. Hertz, E. T., Werra, D. D.: Tabu Search, Local Search in Combinatorial Optimization, 1997, 121–136.
• [2] Antes, J., Derigs, U.: A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows, Technical report, Department of Economics and Computer Science, University of Kln, Germany, 1995.
• [3] B. Gillett, R. M.: A heuristic algorithm for the Vehicle-Dispatch Problem, Operations Research, 22(2), 1974, 340–349.
• [4] Clarke, G., Wright, W.: Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, 12(4), 1964, 568–581.
• [5] Dueck, G., Scheurer, T.: Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90(1), 1990, 161–175.
• [6] G. Laporte, M. Gendreau, J. P. F. S.: Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7(4-5), 2000, 285–300.
• [7] Gascon, V.: Planification du transport et des tourn´ees des personnes ˆag´ees vers les centres de jour du CSSS de Trois-Rivi`eres, Technical report, 2010.
• [8] G.B. Dantzig, J. R.: The truck dispatching problem, Management Science, 6(1), 1959, 80–91.
• [9] Glover, F.: Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13(5), 1986, 533–549.
• [10] Glover, F.: Tabu Search Part I, ORSA Journal on Computing, 1(3), 1989, 190–206.
• [11] Glover, F.: Tabu Search - Part II, INFORMS Journal on Computing, 2(1), 1990, 4–32.
• [12] Laporte, G.: Fifty Years of Vehicle Routing, Transportation Science, 43(4), 2009, 408–416.
• [13] Lin, S., Kernighan, B.W.: An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, 21, 1973, 498–516.
• [14] Pham, V., Dinh, T.: A framework algorithm for a Real-World Variant of the Vehicle Routing Problem, Proceedings of Industrial Engineering and Engineering Management, 2011.
• [15] Shaw, P.: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, CP, Springer-Verlag, 1998.
• [16] Wren, A., Holliday, A.: Computer scheduling of vehicles from one or more depots to a number of delivery points, Operations Research Quarterly, 23, 1972, 333–34.