Vehicle routing problem with service windows, heterogeneous fleets and fractional deliveries

• Marc A. Vieira de Queiroz UEL
• Pedro Casagrande Campos UEL
• Rodolfo Miranda de Barros UEL
• Jacques Duílio Brancher UEL

DOI: https://doi.org/10.5753/sbsi.2012.14424

Abstract

This paper presents a solution to the vehicle routing problem based on the technique of building routes using sequential insertion. The construction of routes is based on savings heuristics which is inspired on classical algorithms, such as developed by Clarke and Wright in 1964. The heuristics employed makes use of four algorithms, Combined Savings (CS), Optimistic Opportunity Savings (OOS), Realistic Opportunity Savings (ROS) and Realistic Opportunity Savings with a route shape parameter (ROSλ). The proposed algorithms are tested by a set of benchmarks and presents graphic and numeric solutions.

Keywords: Vehicle Routing, Heterogeneous fleets, Fractional Deliveries

References

Belfiore, P. and Yoshida Yoshizaki, H. T. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal Of Operational Research, 199(3):750–758.

Brandao, J. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal Of Operational Research, 100(1):180–191.

Clarke, G. and Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4):568–581.

Dror, M. and Trudeau, P. (1989). Savings by Split Delivery Routing. Transportation Science, 23(2):141–145.

Dullaert, W., Janssens, G. K., Sorensen, K., and Vernimmen, B. (2002). New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, 53(11):1232–1238.

Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.

Ho, S. C. and Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31(12):1947–1964.

Liu, F.-h. and Shen, S.-y. (1999). A method for vehicle routing problems with multiple vehicle types and time windows. In Proceedings of Natural Science Council.

Rochat, Y. and Semet, F. (1994). A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland. The Journal of the Operational Research Society, 45(11):1233.

Semet, F. and Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41(4):469–488.

Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2):254–265.