Subscribe Now Subscribe Today
Research Article
 

Study on Multi Depot Heterogeneous Vehicle Routing Problem with an Improved Variable Neighborhood Search Algorithm



Yuexiang Yang, Yingcheng Xu and Li Wang
 
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.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report 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

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  |  

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.
CrossRef  |  Direct 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.
CrossRef  |  Direct 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.
CrossRef  |  Direct 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.
CrossRef  |  Direct 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.
CrossRef  |  Direct Link  |  

Samanta, S. and M.K. Jha, 2011. Multi depot probabilistic vehicle routing problems with a time window: Theory, solution and application. Int. J. Oper. Res. Inform. Syst., 2: 17-41.

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.
CrossRef  |  Direct Link  |  

©  2019 Science Alert. All Rights Reserved