A Goal Programming Model for Single Vehicle Routing Problem with Multiple Routes

Document Type : Research Paper


Industrial Engineering Department, Faculty of Engineering, University of Tehran, P.O. Box 11365-4563


The single vehicle routing problem with multiple routes is a variant of the vehicle routing problem where the vehicle can be dispatched to several routes during its workday to serve a number of customers. In this paper we propose a goal programming model for multi-objective single vehicle routing problem with time windows and multiple routes. To solve the model, we present a heuristic method which exploits an elementary Shortest Path Algorithm with Resource Constraints. Computational results of the proposed algorithm are discussed.


Main Subjects

[1] Azi N., Gendreau M., Potvin J. (2006), An exact algorithm for a single-vehicle routing problem with
time windows and multiple routes; European Journal of Operational Research; Article in press.
[2] Calvete H.I., Gale C., Oliveros M.J. (2007), Valverde B.S., A goal programming approach to vehicle
routing problems with soft time windows; European Journal of Operational Research 177; 1720-1733.
[3] Fisher M.L (1994), Optimal solution of vehicle routing problems using minimum k-trees; Operation
Research 42; 626-642.
[4] Hashimoto H., Ibaraki T., Imahori S., Yagiura M. (2006), The vehicle routing problem with flexible
time windows and traveling times; Discrete Applied Mathematics 154; 1364-1383.
[5] Hong S.C., Park Y.B (1999), A heuristic for bi-objective vehicle routing with time window constraints;
International Journal of Production Economics 62; 249-258.
[6] Irnich S., Funkeb B., Grünert T. (2006), Sequential search and its application to vehicle-routing
problems; Computers & Operations Research 33; 2405–2429.
[7] Lacomme P., Prins C., Sevaux M. (2006), A genetic algorithm for a bi-objective capacitated arc
routing problem; Computers and Operations Research 33; 3473-3493.
[8] Laporte G., Nobert Y. (1987), Exact algorithms for the vehicle routing problem; Annals of Discrete
Mathematics 31; 147-184.
[9] Miller D.L. (1995), A matching based exact algorithm for capacitated vehicle routing problem; ORSA
Journal on Computing 7; 1-9.
[10] Ombuki B., Ross B.J., Hanshar F. (2006), Multi-Objective Genetic Algorithms for Vehicle Routing
Problem with Time Windows; Applied Intelligence 24; 17–30.
[11] Solomon M. (1987), Algorithms for the vehicle routing and scheduling problems with time window
constraints; Operations Research 35; 254–65.
[12] Tan K.C., Chew Y.H., Lee L.H. (2006), A hybrid multi-objective evolutionary algorithm for solving
truck and trailer vehicle routing problems; European Journal of Operational Research 172; 855-885.
[13] Toth P., Vigo D. (Eds.) (2002), The Vehicle Routing Problem; SIAM Monographs on Discrete
Mathematics and Applications 9(l).