A Column Generation for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem
Submitted: 2016-06-11
|Accepted: 2017-06-09
|Published: 2017-07-28
Downloads
Keywords:
Open Vehicle Routing Problem, Heterogeneous Fixed Fleet, NP-hard Problems, Column Generation
Supporting agencies:
Abstract:
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.
References:
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
