Skip to main content
SpringerLink
Log in

An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, a carton heterogeneous vehicle routing problem with a collection depot is presented, which can collaboratively pick the cartons from several carton factories to a collection depot and then from the depot to serve their corresponding customers by using of heterogeneous fleet. Since the carton heterogeneous vehicle routing problem with a collection depot is a very complex problem, particle swarm optimization (PSO) is used to solve the problem in this paper. To improve the performance of the PSO, a self-adaptive inertia weight and a local search strategy are used. At last, the model and the algorithm are illustrated with two test examples. The results show that the proposed PSO is an effective method to solve the multi-depot vehicle routing problem, and the carton heterogeneous vehicle routing problem with a collection depot. Moreover, the proposed model is feasible with a saving of about 28 % in total delivery cost and could obviously reduce the required number of vehicles when comparing to the actual instance.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  • Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693–1702.

    Article  Google Scholar 

  • Athanasopoulos, T., & Minis, L. (2013). Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework. Annals of Operations Research, 206(1), 1–22.

    Article  Google Scholar 

  • Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 1(8), 41–48.

    Article  Google Scholar 

  • Chao, M. I., Golden, B. L., & Wasil, E. A. (1993). A new heuristic for the multi-depot vehicle routing problem that improves upon bestknown solutions. American Journal of Mathematical and Management Sciences, 13, 371–406.

    Article  Google Scholar 

  • Chatterjee, A., & Siarry, P. (2006). Nonlinear inertia weight variation for dynamic adaption in particle swarm optimization. Computer and Operations Research, 33(3), 859–871.

    Article  Google Scholar 

  • Chen, B. Y., Lam, W. H. K., Sumalee, A., & Li, Z. L. (2012). Reliable shortest path finding in stochastic networks with spatial correlated link travel times. International Journal of Geographical Information Science, 26, 365–386.

    Article  Google Scholar 

  • Chen, B. Y., Lam, W. H. K., Sumalee, A., Li, Q. Q., Shao, H., & Fang, Z. X. (2013a). Finding reliable shortest paths in road networks under uncertainty. Networks & Spatial Economics, 13, 123–148.

    Article  Google Scholar 

  • Chen, B. Y., Lam, W. H. K., Li, Q. Q., Sumalee, A., & Yan, K. (2013). Shortest path finding problem in stochastic time-dependent road networks with stochastic first-in-first-out property. IEEE Transactions on Intelligent Transportation Systems, 14(4), 1907–1917.

  • Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle dispatching problem. Journal of the Operational Research Society, 20, 309–318.

    Article  Google Scholar 

  • Cordeau, J. F., & GendreauMand Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105–119.

    Article  Google Scholar 

  • Crevier, B., Cordeau, J. F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research., 176(2), 756–773.

    Article  Google Scholar 

  • Eberhart, R. C., & Shi, Y. H. (2001). Tracking and optimizing dynamic systems with particle swarms. Congress on Evolutionary Computation, Korea, 1, 94–100.

    Google Scholar 

  • Duan, Q. Y., Gupta, V. K., & Sorooshian, S. (1993). Shuffled complex evolution approach for effective and efficient minimization. Journal of optimization theory and applications, 76(3), 501–521.

    Article  Google Scholar 

  • Gillett, B. E., & Johnson, J. G. (1976). Multi-terminal vehicle-dispatch algorithm. Omega, 4, 711–718.

    Article  Google Scholar 

  • Goncalves, G. M., Gouveia, L., & Pato, M. V. (2014). An improved decomposition-based heuristic to design a water distribution network for an irrigation system. Annals of Operations Research, 219(1), 141–167.

    Article  Google Scholar 

  • Imran, A., Salhi, S., & Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 197(2), 509–518.

    Article  Google Scholar 

  • Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, Aystralia, (pp. 1942–1948).

  • Lin, T. L., Horng, S. J., Kao, T. W., Chen, Y. H., Run, R. S., Chen, R. J., et al. (2010). An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications, 37, 2629–2636.

    Article  Google Scholar 

  • Liu, X. F., & Chen, S. (2008). Research on profit allocation of common delivery. Service operations and logistics, and informatics. IEEE/SOLI, 2, 1505–1508.

    Google Scholar 

  • Mohemmed, A. W., Sahoo, N. C., & Geok, T. K. (2008). Solving shortest path problem using particle swarm optimization. Applied Soft Computing, 8(4), 1643–1653.

    Article  Google Scholar 

  • Mu, Q. X., & Eglese, R. W. (2013). Disrupted capacitated vehicle routing problem with order release delay. Annals of Operations Research, 207(1), 201–216.

    Article  Google Scholar 

  • Nickabadi, A., Ebadzadeh, M. M., & Safabakhsh, R. (2011). A novel particle swarm optimization algorithm with adaptive inertia weight. Applied Soft Computing, 11(4), 3658–3670.

    Article  Google Scholar 

  • Nelder, J. A., & Mead, R. (1965). A simplex method for function minimization. Computer Journal, 7(4), 308–313.

    Article  Google Scholar 

  • Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229–235.

    Article  Google Scholar 

  • Shi, Y., & Eberhart, R. (2001). Fuzzy adaptive particle swarm optimization. In Congress on Evolutionary Computation Seoul, Korea.

  • Yao, B. Z., Hu, P., Lu, X. H., Gao, J. J., & Zhang, M. H. (2014a). Transit network design based on travel time reliability. Transportation Research Part C, 43, 233–248.

  • Yao, B. Z., Hu, P., Zhang, M. H., & Jin, M. Q. (2014b). A support vector machine with the tabu search algorithm for freeway incident detection. International Journal of Applied Mathematics and Computer Science, 24(2), 397–404.

  • Yao, B. Z., Hu, P., Zhang, M. H., & Wang, S. (2013). Artificial bee colony algorithm with scanning strategy for periodic vehicle routing problem. SIMULATION: Transactions of The Society for Modeling and Simulation International, 89(6), 762–770.

    Article  Google Scholar 

  • Yao, Q. Z., Zhu, X. Y., & Kuo, W. (2014c). A Birnbaum-importance based genetic local search algorithm for component assignment problems. Annals of Operations Research, 212(1), 185–200.

  • Yu, B., & Yang, Z. Z. (2011). An ant colony optimization model: The period vehicle routing problem with time windows. Transportation Research Part E, 47(2), 166–181.

    Article  Google Scholar 

  • Yu, B., Yang, Z. Z., Sun, X. S., Yao, B. Z., Zeng, Q. C., & Jeppesen, E. (2011a). Parallel genetic algorithm in bus route headway optimization. Applied Soft Computing, 11(8), 5081–5091.

  • Yu, B., Yang, Z. Z., Xie, J. X. (2011b). A parallel improved ant colony optimization for multi-depot vehicle routing problem. Journal of The Operational Research Society, 62(1),183–188.

  • Yu, B., Yang, Z. Z., & Yao, B. Z. (2009). An improved ant colony optimization for vehicle routing problem. European Journal Of Operational Research, 196(1), 171–176.

    Article  Google Scholar 

  • Yu, B., Zhu, H. B., Cai, W. J., Ma, N., & Yao, B. Z. (2013). Two-phase optimization approach to transit hub location—The case of Dalian. Journal of Transport Geography, 33, 62–71.

    Article  Google Scholar 

  • Yue, M., & Sun, W. (2011). Non-linear adaptive controller with a variable adaptation rate for a simulated model of an electrohydraulic actuator. Proceedings of Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering., 225(5), 603–609.

    Google Scholar 

  • Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2010). An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 202(2), 401–411.

    Article  Google Scholar 

  • Zhang, R. H., & Luo, G. R. (2008). Benefit of the common distribution based on the Shapley value. Wuhan University of Technology Journal, 30, 50–54.

    Google Scholar 

  • Zhang, T., Chaovalitwongse, W. A., & Zhang, Y. J. (2012). Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Computers & Operations Research, 39(10), 2277–2290.

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported by the National Natural Science Foundation of China 51208079 and 51108053, the Trans-Century Training Program Foundation for Talents from the Ministry of Education of China NCET-12-0752, Ministry of Housing and Urban-Rural Development K520136 and the Fundamental Research Funds for the Central Universities 3013-852019.

Author information

Authors and Affiliations

  1. School of Automotive Engineering, Dalian University of Technology, Dalian, 116024, China

    Baozhen Yao, Ping Hu, Junjie Gao & Mingheng Zhang

  2. Transportation Management College, Dalian Maritime University, Dalian, 116026, China

    Bin Yu

Authors
  1. Baozhen Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ping Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Junjie Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Mingheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Bin Yu or Mingheng Zhang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yao, B., Yu, B., Hu, P. et al. An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Ann Oper Res 242, 303–320 (2016). https://doi.org/10.1007/s10479-015-1792-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-015-1792-x

Keywords

Search

Navigation