Volume 1 Issue 1 pp. 55-64 July, 2010


A particle swarm approach to solve vehicle routing problem with uncertain demand: A drug distribution case study


Babak Farhang Moghadam and Seyed Mohammad Seyedhosseini


During the past few years, there have tremendous efforts on improving the cost of logistics using varieties of Vehicle Routing Problem (VRP) models. In fact, the recent rise on fuel prices has motivated many to reduce the cost of transportation associated with their business through an improved implementation of VRP systems. We study a specific form of VRP where demand is supposed to be uncertain with unknown distribution. A Particle Swarm Optimization (PSO) is proposed to solve the VRP and the results are compared with other existing methods. The proposed approach is also used for real world case study of drug distribution and the preliminary results indicate that the method could reduce the unmet demand significantly.


DOI: 10.5267/j.ijiec.2010.01.005

Keywords: Meta-heuristic, PSO, VRP, Taguchi method, Robust Optimization

References

Ai, J., & Kachitvichyanukul, V. (2009.a). A particle swarm optimization for the vehicle routing problem with simultaneous pickupand delivery. Computers & Operations Research, 36, 1693-1702.

Ai, J., & Kachitvichyanukul, V. (2009.b). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56 (1), 380-387.

Ai, J., & Kachitvichyanukul, V. (2009.c). A Particle Swarm Optimisation for Vehicle Routing Problem with Time Windows. International Journal of Operational Research, 6 (4), 519-537.

Ai, J., & Kachitvichyanukul, V. (2008). A Study on Adaptive Particle Swarm Optimization for Solving Vehicle Routing Problems. The 9th Asia Pacific Industrial Engineering and Management Systems Conference.

Andersson, H., Hoff, A., Christiansen, M., Hasle, G. & Løkketangen, A. (2010). Industrial aspects and literature survey: Combined inventory management and routing, Computers & Operations Research, 37(9), 1515-1536.

Bertsimas, D. J. (1992). A vehicle routing problem with stochastic demand. Operations Research , 40 (3), 574-585.

Chen, A., Yang, G., & Wu, Z. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University Science, 7 (4), 607-614.

Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568–589.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6, 80-91.

Dror, M. (1993). Modeling vehicle routing with uncertain demands as a stochastic program. European Journal of Operational Research , 64, 432–441.

Golden, B. L., & Yee, J. R. (1979). A framework for probabilistic vehicle routing. AIIE Transactions, 11, 109-112.

Graves, S. C., Rinooy Kan, A., & Zipkin, P. (1993). Logistics of Production and Inventories: Handbooks in OR & MS (Vol. 4). Elsevier Science.

Garaix, T., Artigues, C., Feillet, D. & Josselin, D. (2010). Vehicle routing problems with alternative paths: An application to on-demand transportation, European Journal of Operational Research, 204, 62-75.

Jaillet, P., & Odoni, A. (1988). The Probabilistic Vehicle Routing Problem, in Vehicle Routing; Methods and Studies. In B. L. Golden, & A. A. Assad, (Eds.) Amsterdam: North Holland.

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. IEEE Int. Conf. Neural Networks, 1942-1948.

Lenstra, J. K., & Rinnooy Kan, A. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11, 221-227.

Marinakis, Y. & Marinaki, M. (2010). A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem, Computers and Operations Research, 37 (3), 432-442.

Önüt, S., Tuzkaya, R. U., & Doğaç, B. (2008). A particle swarm optimization algorithm for the multiple level warehouse layout design problem. Computers & Industrial Engineering, 54 (4), 783-799.

Shi, X. H., Liang, Y. C., Lee, H. P., Lu, C., & Wang, Q. X. (2007). Particle swarm optimization based algorithms for TSP and generalized TSP. Information Processing Letters, 103 (5), 169-176.

Stewart, W. R., & Golden, B. L. (1983). Stochastic vehicle routing. European Journal of Operational Research, 14, 371–385.

Tao, Z., Chunmei, Z., Yuejie, Z., & Chuoya, Y. (2008). A Mixed PSO algorithm for the VRPSPD. Control and Decision Conference, (pp. 4017-4021).

Veeramachaneni, K., Peram, T., Mohan, C., & Osadciw, L. (2003). Optimization using particle swarm with near neighbor interactions. Genetic and Evolutionary Computation Conference.