Fleet Size and Mix Vehicle Routing Problem, Constructive Routing Heuristics, Vehicle Routing Problem, Routing Algorithm, Ochi’s routing approach

Abstract

A New Heuristic Routing Algorithm for Fleet Size and Mix Vehicle Routing Problem

Abstract

Ochi’s approach solves the heterogenous vehicle routing problem using the constraint having fixed costs as a multiplier of residuals. However, in this approach, there is not any information about which vehicle will be assigned to the route related to this constraint. In our study, Ochi’s approach is interpreted again in terms of vehicle capacity and number of customers assigned to each route. The proposed routing approach is taking the higher capacity vehicle for improving the performance. Then the solution phases of a sample problem are shown by using the given algorithm. In order to highlight the performance of the routing approach, Golden’s 12 test problems (Fleet Size and Mix Vehicle Routing Problem with Fixed Cost) are used. It is seen that the proposed method has better average time complexity and equal cost performances than Ochi’s routing approach.  Therefore, the solutions with higher capacity vehicle of the proposed method that uses vehicle type information are better than those of the methods that use residual cost based on the vehicle type information.

Keywords

• Fleet Size and Mix Vehicle Routing Problem
• Constructive Routing Heuristics
• Vehicle Routing Problem
• Routing Algorithm
• Ochi’s routing approach

References

1. L. Ochi, D. Vianna, L. M. Drummond and A. Victor, "A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet," Parallel And Distributed Processing, pp. 216-224, 1998.
2. C. Lima, M. Goldbarg and E. Goldbarg, "A Memetic Algorithm for Heterogeneous Fleet Vehicle Routing Problem," Mathematics, vol. 18, pp. 171-176, 2004. Notes in Discrete
3. R. Baldacci, M. Battarra and D. Vigo, "Routing a Heterogeneous Fleet of Vehicles," Operations Research/Computer Science Interfaces, vol. 43, pp. 3-27, 2008.
4. A. Subramanian, P. H. V. Penna, E. Uchoa and L. S. Ochi, "A Hybrid Algorithm for the Heterogeneous Fleet Vehicle Routing Problem," European Journal of Operational Research, vol. 221, pp. 285-295, 2012.
5. G. Clarke and J. W. Wright, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, vol. 12, no. 4, pp. 568-581, 1964.
6. A. E. Gillett and L. R. Miller, "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, vol. 22, no. 2, pp. 340-349, 1974.
7. M. L. Fisher and R. Jaikumar, "A Generalized Assignment Networks, vol. 11, no. 2, p. 109–124, 1981. Vehicle Routing,"
8. M. Desrochers and T. W. Verhoog, "A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem," Computers and Operations Research, vol. 18, no. 3, pp. 263-274, 1991.

9. S. Salhi and G. K. Rand, "Incorporating Vehicle Routing Into the Vehicle Fleet Composition Problem," European Journal of Operational Research, vol. 66, no. 3, pp. 313-330, 1993.
10. I. H. Osman and S. Salhi, "Local Search Strategies for the Vehicle Fleet Mix Problem," in Modern Heuristic Search Methods, Chichester, Wiley, 1996, pp. 131-154.
11. S.-C. Liu and H.-J. Lu, "A hybrid heuristic method for the fleet size and mix vehicle routing problem," Journal of Industrial and Production Engineering, vol. 30, no. 3, p. 181–189, 2013.
12. A. L. Golden, A. A. Assad, L. Levy and F. Gheysens, "The Fleet Size and Mix Vehicle Routing Problem," Computers and Operations Research, pp. 49-66, 1984.
13. S. Liu, W. Huang and H. Ma, "An Effective Genetic Algorithm for the Fleet Size and Mix Vehicle Routing Problems," Transportation Research Part E, vol. 45, pp. 434-445, 2009.
14. M. G. Kay, "Matlog: Logistics Engineering Matlab 2013. Toolbox," http://www.ise.ncsu.edu/kay/matlog/. [Accessed 16 2 2013]. [Online]. Available:
15. H. Yaman, "Formulations and Valid Ineaqualities for the Heteogenous Vehicle Routing Problem," Mathematical Programming, vol. 106, pp. 365-390, 2006.
16. A. D. Taillard, "A Heuristic Column Generation Method for the Heterogeous Fleet Vehicle Routing Problem," RAIRO Rech. Oper., vol. 33, pp. 1-14, 1999.
17. M. Gendreau, G. Laporte, C. Musaraganyi and E. D. Taillard, "A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem," Computers and Operations Research, vol. 26, pp. 1153-1173, 1999.
18. N. Wassan and I. Osman, "Tabu Search Variants for the Mix Fleet Vehicle Routing Problem," Journal of the Operational Research Society, vol. 53, pp. 768- 782, 2002.
19. A. Choi and D.-W. Tcha, "A Column Generation Approach to the," Computers and Operations Research, vol. 34, p. 2080–2095, 2007.
20. J. Brandao, "A Deterministic Tabu Search Algorithm for the Fleet Size and Mix Vehicle Routing Operational Research, vol. 195, no. 3, pp. 716-728, 2009. Journal of
21. A. H. Liu and S. Y. Shen, "The Fleet Size and Mix Vehicle Routing Problem with Time Windows," The Journal of the Operational Research Society, vol. 50, no. 7, pp. 721-732, 1999.
22. J. Renaud and F. F. Boctor, "A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing Operational Research, vol. 140, no. 3, pp. 618-628, 2002. Journal of