A Column Generation for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem

Majid Yousefikhoshbakht, Azam Dolatnejad


This paper addressed the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), in which the vehicles are not required to return to the depot after completing a service. In this new problem, the demands of customers are fulfilled by a heterogeneous fixed fleet of vehicles having various capacities, fixed costs and variable costs. This problem is an important variant of the open vehicle routing problem (OVRP) and can cover more practical situations in transportation and logistics. Since this problem belongs to NP-hard Problems, An approach based on column generation (CG) is applied to solve the HFFOVRP. A tight integer programming model is presented and the linear programming relaxation of which is solved by the CG technique. Since there have been no existing benchmarks, this study generated 19 test problems and the results of the proposed CG algorithm is compared to the results of exact algorithm. Computational experience confirms that the proposed algorithm can provide better solutions within a comparatively shorter period of time.


Open Vehicle Routing Problem; Heterogeneous Fixed Fleet; NP-hard Problems; Column Generation

Full Text:



Aleman, R. E., Hill, R. R. (2010). A tabu search with vocabulary building approach for the vehicle routing problem with split demands, International Journal of Metaheuristics, 1(1), 55-80. https://doi.org/10.1504/IJMHEUR.2010.033123

Anbuudayasankar S.P., Ganesh b, K., Lenny Koh S.C., Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications, 39, 2296-2305. https://doi.org/10.1016/j.eswa.2011.08.009

Brandão J. (2009). A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 195, 716-728. https://doi.org/10.1016/j.ejor.2007.05.059

Çatay, B. (2010). A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Expert Systems with Applications, 37(10), 6809-6817. https://doi.org/10.1016/j.eswa.2010.03.045

Dantzig, G., Ramser, J. (1959). The truck dispatching problem. Management Science, 6, 80-91. https://doi.org/10.1287/mnsc.6.1.80

Gendreau, M., Guertin, F., Potvin, J. Y., Séguin, R. (2006). Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Part C, 14, 157-174. https://doi.org/10.1016/j.trc.2006.03.002

Gendreau, M., Laporte, G., Musaraganyi, C., Taillard, E. D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers and Operations Research, 26, 1153-1173. https://doi.org/10.1016/S0305-0548(98)00100-2

Lei, H., Laporte, G., Guo, B., (2011). The capacitated vehicle routing problem with stochastic demands and time windows. Computers & Operations Research, 38(12), 1775-1783. https://doi.org/10.1016/j.cor.2011.02.007

Li, X., Leung, S. C. H., Tian, P. (2012). A multi start adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. Expert Systems with Applications, 39, 365-374. https://doi.org/10.1016/j.eswa.2011.07.025

Li, X., Tian, P., Aneja, Y. P. (2010). An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Transportation Research Part E, 46, 1111-1127. https://doi.org/10.1016/j.tre.2010.02.004

Penna, P. H. V., Subramanian, A., Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201-232. https://doi.org/10.1007/s10732-011-9186-y

Saadati Eskandari, Z., YousefiKhoshbakht, M. (2012). Solving the Vehicle Routing Problem by an Effective Reactive Bone Route Algorithm, Transportation Research Journal, 1(2), 51-69.

Subramanian, A., Drummond, L., Bentes, C., Ochi, L.S., Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11), 1899-1911. https://doi.org/10.1016/j.cor.2009.10.011

Syslo, M., Deo, N., Kowalik, J. (1983). Discrete Optimization Algorithms with Pascal Programs, Prentice Hall.Taillard, E. D. (1999). A heuristic column generation method for the heterogeneous fleet VRP, RAIRO Operations Research, 33, 1-14. https://doi.org/10.1051/ro:1999101

Tarantilis, C. D., Kiranoudis, C. T. (2007). A Flexible Adaptive Memory-based Algorithm for Real-life Transportation Operations: Two Case Studies from Dairy and Construction Sector. European Journal of Operational Research, 179, 806-822. https://doi.org/10.1016/j.ejor.2005.03.059

Wang, H. F., Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62, 84-95. https://doi.org/10.1016/j.cie.2011.08.018

YousefiKhoshbakht, M., Didehvar, F. and Rahmati, F. (2014). Solving the Heterogeneous Fixed Fleet Open Vehicle Routing Problem by a Combined Meta-heuristic Algorithm. International Journal of Production Research, 52(9), 2565-2575. https://doi.org/10.1080/00207543.2013.855337

Yousefikhoshbakht, M., Dolatnejad, A., Didehvar, F., Rahmati, F. (2016). A Modified Column Generation to Solve the Heterogeneous Fixed Fleet Open Vehicle Routing Problem, Journal of Engineering, https://doi.org/10.1155/2016/5692792

YousefiKhoshbakht, M. and Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(11), 1-9. https://doi.org/10.1186/2251-712X-8-11

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives- 4.0 International License 

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317   https://doi.org/10.4995/ijpme