Yuexiang Yang
Quality Management Branch, China National Institute of Standardization, Beijing, 100191, China
Yingcheng Xu
Quality Management Branch, China National Institute of Standardization, Beijing, 100191, China
Li Wang
School of Economics and Management, Beihang University, Beijing 100191, China
ABSTRACT
This study deals with the Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows (MDHVRPTW) which is complex and still not resolved well. The objective is to determine the best fleet composition as well as the set of routes that minimize the total cost with known demands. To solve the problem, mathematical model of the MDHVRPTW is constructed and an improved variable neighborhood search algorithm is proposed. In the algorithm, the hybrid operators of insert and exchange are used to achieve the shaking process and the later optimization process is presented to improve the solution space, the best-improvement strategy is adopted which make the algorithm can achieve a better balance in the solution quality and running time. The idea of simulated annealing is introduced to take control of the acceptance of new solutions. The developed algorithm was tested in benchmark instances. The results obtained are quite competitive with those found in the literature and new improved solutions are reported. And finally the proposed model and algorithm is applied to the large water project in China to solve the allocation of vehicles and routes, it demonstrates that the systematic method is effective and feasible.
PDF References Citation
How to cite this article
Yuexiang Yang, Yingcheng Xu and Li Wang, 2013. Study on Multi Depot Heterogeneous Vehicle Routing Problem with an Improved
Variable Neighborhood Search Algorithm. Information Technology Journal, 12: 7137-7142.
DOI: 10.3923/itj.2013.7137.7142
URL: https://scialert.net/abstract/?doi=itj.2013.7137.7142
DOI: 10.3923/itj.2013.7137.7142
URL: https://scialert.net/abstract/?doi=itj.2013.7137.7142
REFERENCES
- Adibi, M.A., M. Zandieh and M. Amiri, 2010. Multiobjective scheduling of dynamic job shop using variable neighborhood search. Expert Syst. Appl., 37: 282-287.
CrossRef - Subramanian, A., P.H. Vaz Penna, E. Uchoa and L.S. Ochi, 2012. A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res., 221: 285-295.
CrossRefDirect Link - Choi, E. and D.W. Tcha, 2007. A column generation approach to the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res., 34: 2080-2095.
CrossRefDirect Link - Gendreau, M., F. Guertin, J.V. Potvin and R. Seguin, 2006. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transport. Res. Part C, 14: 157-174.
Direct Link - Hansen, P., J. Brimberg, D. Urosevic and N. Mladenovic, 2007. Primal-dual variable neighborhood search for the simple plant-location problem. Informs J. Comput., 19: 552-564.
Direct Link - Hansen, P., N. Mladenovic and D. Perez-Britos, 2001. Variable neighborhood decomposition search. J. Heuristics, 7: 335-350.
CrossRefDirect Link - Imran, A., S. Salhi and N.A. Wassan, 2009. Variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res., 197: 509-518.
CrossRefDirect Link - Lee, Y.H., J.I. Kim, K.H. Kang and K.H. Kim, 2008. A heuristic for vehicle fleet mix problem using Tabu search and set partitioning. J. Oper. Res. Soc., 59: 833-841.
CrossRefDirect Link - Salhi, S., N. Wassan and M. Hajarat, 2013. The fleet size and mix vehicle routing problem with backhauls: Formulation and set partitioning-based heuristics. Transport. Res. Part E: Logistics Transport. 56: 22-35.
CrossRefDirect Link