Abstract
A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The variation is caused by congestion that is typically greatest during morning and evening rush hours. The algorithm is used to schedule a fleet of delivery vehicles operating in the South West of the United Kingdom for a sample of days. The results demonstrate how conventional methods that do not take time-varying speeds into account when planning, except for an overall contingency allowance, may still lead to some routes taking too long. The results are analysed to show that in the case study using the proposed approach can lead to savings in CO2 emissions of about 7%.
This is a preview of subscription content, log in via an institution to check access.
References
Eglese RW, Maden W and Slater A (2006). A Road Timetable™ to aid vehicle routing and scheduling. Comput Opns Res 33: 3508–3519.
Fleischmann B, Gietz M and Gnutzmann S (2004). Time-varying travel times in vehicle routing. Trans Sci 38: 160–173.
Gendreau M, Hertz A and Laporte G (1994). A tabu search heuristic for the vehicle routing problem. Mngt Sci 40: 1276–1290.
Ichoua S, Gendreau M and Potvin J-Y (2003). Vehicle dispatching with time-dependent travel times. Eur J Opl Res 144: 379–396.
Ichoua S, Gendreau M and Potvin J-Y (2006). Exploiting knowledge about future demands for real-time vehicle dispatching. Trans Sci 40: 211–225.
Maden W (2006). Models and heuristic algorithms for complex routing and scheduling problems. PhD Thesis, Lancaster University Management School.
Malandraki C and Daskin MS (1992). Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Trans Sci 26: 185–200.
McKinnon AC and Piecyk MI (2009). Measurement of CO2 emissions from road freight transport: A review of UK experience. Working Paper, Logistics Research Centre, School of Management and Languages, Heriot-Watt University, Edinburgh EH14 4AS. Also available to download from http://www.greenlogistics.org/ (accessed 3 July 2009).
Potvin J-Y and Rousseau J-M (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: 245–265.
Taillard ED, Badeau P, Gendreau M, Guertin F and Potvin J-Y (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Trans Sci 31: 170–186.
Taniguchi E and Shimamoto H (2004). Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times. Trans Res Part C 12: 235–250.
Toth P and Vigo D (eds) (2002). The Vehicle Routing Problem. SIAM: Philadelphia.
Van Woensel T, Kerbache L, Peremans H and Vandaele N (2008). Vehicle routing with dynamic travel times: a queueing approach. Eur J Opl Res 186: 990–1007.
Acknowledgements
This research was supported by the Engineering and Physical Sciences Research Council Green Logistics project: Grant No. EP/D043328/1.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Maden, W., Eglese, R. & Black, D. Vehicle routing and scheduling with time-varying data: A case study. J Oper Res Soc 61, 515–522 (2010). https://doi.org/10.1057/jors.2009.116
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.116