Abstract
This paper proposes new proximity measures for assignment algorithms for the Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW). Given the intrinsic difficulty of this problem class, two-step approximation methods of the type ‘cluster first, route second’ seem to be the most promising for practical size problems. The focus is on the clustering phase, the assignment of customers to depots. Our approach is to extend the existing metrics with time windows. New measures that include time windows and distances are added to two assignment heuristics, that previously only used distance to evaluate proximity between customers and depots. A computational study of their performance is presented, which shows that the inclusion of time windows in the measures of proximity gives better results, in terms of routing, than only using the distance.
Similar content being viewed by others
References
Assad A, Ball M, Bodin L and Golden B (1983). Routing and scheduling of vehicles and crews: the state of the art. Comput Opns Res 10: 63–211.
Lenstra J and Rinnooy Kan A (1981). Complexity of vehicle routing and scheduling problems. Networks 11: 221–228.
Tansini L (2001). Algoritmos de Asignación para MDVRPTW. Master Thesis–PEDECIBA, 2001, Instituto de Computación, Facultad de Ingeniería, UDELAR.
Caseau Y and Laburthe F (1998). A fast heuristic for large routing problems. Presented at IFORS 98, Kaunas, Lithuania.
Laporte G, Gendreau M, Potvin JY and Semet F (2000). Classical and modern heuristics for the vehicle routing problem. Int Trans Opl Res 7: 285–300.
Toth P and Vigo D (1998). The granular tabu search (and its application to the vehicle routing problem). Working paper, DEIS, University of Bologna.
Cordeau JF, Laporte G and Mercier A (2001). A unified tabu search heuristic for vehicle routing problems with time windows. J Opl Res Soc 52: 928–936.
Reimann M, Doerner K and Hartl RF (2003). Analyzing a unified ant system for the VRP and some of its variants. In: Günther et al (ed). EvoWorkshops 2003, Lecture Notes in Computer Science, Vol 2611, Springer-Verlag, Berlin, Heidelberg, pp 300–310.
Rousseau LM, Gendreau M, Pesant G and Focacci F (2004). Solving VRPTWs with constraint programming based column generation. Ann Opl Res 130: 199–216.
Berger J, Barkaoui M and Bräysy O (2001). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Working paper, Defense Research Establishment Valcartier, Canada.
Czech ZJ and Czarnas P (2002). Parallel simulated annealing for the vehicle routing problem with time windows. Presented at the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain.
Sa’adah P and Paechter B (2004). Improving vehicle routing using a customer waiting time colony. In: Goos G, Hartmanis J and van Leeuwen J (eds). EvoCOP 2004, Lecture Notes in Computer Science, Vol 3004, Springer-Verlag, Berlin, pp 188–198.
Bramel J and Simchi-Levi D (1997). On the effectiveness of set covering formulations for the vehicle routing problem with time windows. Ops Res 45: 295–301.
Potvin J and Rousseau J (1993). A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. Eur J Opl Res 66: 331–340.
Solomon M (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Opns Res 35: 254–264.
Salhi S and Nagy G (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J Opl Res Soc 50: 1034–1042.
Ioannou G, Kritikos M and Prastacos G (2001). A greedy look-ahead heuristic for the vehicle routing problem with time windows. J Opl Res Soc 52: 523–537.
Cordeau JF, Gendreau M and Laporte G (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30: 105–119.
Salhi S and Sari M (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. Eur J Opl Res 103: 95–112.
Desaulniers G, Lavigne J and Soumis F (1998). Multi-depot vehicle scheduling problems with time windows and waiting costs. Eur J Opl Res 111: 479–494.
Russell R and Igo W (1979). An assignment routing problem. Networks 9: 1–17.
Urquhart M, Viera O, Gonzalez M and Cancela H (1997). Vehicle routing techniques applied to a milk collection problem. Presented at INFORMS Fall Meeting, Dallas, TX, USA.
Foulds LR and Wilson JM (1997). A variation of the generalized assignment problem arising in the New Zealand Dairy Industry. Ann Opns Res 69: 105–114.
Giosa D, Tansini L and Viera O (1999). Assignment algorithms for the multi-depot vehicle routing problem. Presented at SADIO, Buenos Aires, Argentina.
Berry M and Lindoff G 1995. Data Mining Techniques: for Marketing, Sales and Customer Support. John Wiley & Sons: Chichester.
Giosa D, Tansini L and Viera O (2002). New assignment algorithms for the multi-depot vehicle routing problem. J Opl Res Soc 53: 977–984.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tansini, L., Viera, O. New measures of proximity for the assignment algorithms in the MDVRPTW. J Oper Res Soc 57, 241–249 (2006). https://doi.org/10.1057/palgrave.jors.2601979
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2601979