Multiple demands vehicle routing problem with time windows and service order constraints

被引：0
|
作者：
Li Z.-P. [1 ]
Zhang Y.-W. [1 ]
机构：
[1] College of Information Science, Beijing Wuzi University, Beijing
来源：
Kongzhi yu Juece/Control and Decision | 2019年 / 34卷 / 07期
关键词：
Joint optimal genetic algorithm; Mixed integer programming; Multiple demands; Service order constraint; Time windows; Vehicle routing problem;
D O I：
10.13195/j.kzyjc.2017.1630
中图分类号：
学科分类号：
摘要：
A vehicle routing problem with multiple demands is investigated, where each type of demand needs a special type of vehicles to provide service and the service order of one customer's multiple demands is fixed. Considering the constraints of time windows, the service order of multiple demands, the interval between different service, the capacity and total running time of each vehicle, a mix integer programming model is formulated to minimize the total costs of all vehicles. A joint optimal genetic algorithm is developed for solving the model. The effectiveness of the algorithm is verified by simulations on instances with two types of demands derived from the VRP benchmarks. This paper not only extends the classical single-demand vehicle routing problem to the multiple demands case, but also formulates a mathematical model of the multiple demands vehicle routing problem with constraints and designs an effective algorithm for solving the model, which provides a decision basis for solving practical problems. © 2019, Editorial Office of Control and Decision. All right reserved.
引用
收藏
页码：1565 / 1570
页数：5
相关论文
共 15 条
  • [1] Wang P.D., Tang G.Y., Yang L., Improved ant colony algorithm for capacitated vehicle routing problems, Control and Decision, 27, 11, pp. 1633-1638, (2012)
  • [2] Zhang X.N., Fan H.M., Hybrid scatter search algorithm for capacitated vehicle routing problem, Control and Decision, 30, 11, pp. 1937-1944, (2015)
  • [3] Shi J.L., Zhang J., Model and algorithm for split delivery vehicle routing problem with stochastic customers, Control and Decision, 32, 2, pp. 213-222, (2017)
  • [4] Kachitvichyanukul V., Sombuntham P., Kunnapapdeelert S., Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO, Computers & Industrial Engineering, 89, pp. 125-136, (2015)
  • [5] Kim K.C., Sun J.U., Lee S.W., A hierarchical approach to vehicle routing and scheduling with sequential services using the genetic algorithm, Int J of Industrial Engineering Theory Applications and Practice, 20, 1, pp. 99-113, (2013)
  • [6] Pang H.J., Ding Y.Z., Optimization for vehicle routeing with separated delivery and installation of products based on soft time windows, J of Shanghai Maritime University, 33, 1, pp. 20-25, (2012)
  • [7] Bae H., Moon I., Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles, Applied Mathematical Modeling, 40, 13, pp. 6536-6549, (2016)
  • [8] Liu R., Xie X., Augusto V., Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, European J of Operational Research, 230, 3, pp. 475-486, (2013)
  • [9] Avci M., Topaloglu S., An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries, Computers and Industrial Engineering, 83, pp. 15-29, (2015)
  • [10] Zhou R., Shen W.L., Liu M.Z., A hybrid discrete particle swarm optimization algorithm for vehicle routing problem with time windows and simultaneous pickup and delivery, China Mechanical Engineering, 27, 4, pp. 494-502, (2016)
12