Skip to main content
Log in

New measures of proximity for the assignment algorithms in the MDVRPTW

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6

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.

    Article  Google Scholar 

  • Lenstra J and Rinnooy Kan A (1981). Complexity of vehicle routing and scheduling problems. Networks 11: 221–228.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Rousseau LM, Gendreau M, Pesant G and Focacci F (2004). Solving VRPTWs with constraint programming based column generation. Ann Opl Res 130: 199–216.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Solomon M (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Opns Res 35: 254–264.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Cordeau JF, Gendreau M and Laporte G (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30: 105–119.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Russell R and Igo W (1979). An assignment routing problem. Networks 9: 1–17.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to L Tansini.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2601979

Keywords

Navigation