利益付き配送計画問題(Vehicle Routing Problem with Profits: VRPP): この問題は必ずしも全顧客を訪問する必要がない最大化問題である。目標としては各顧客に設けられた利益を時間制限の範囲内で各車両が、顧客は一度のみ訪問ができるという条件下で回収した利益の総和を最高する問題である。また車両は開始時と終了時に必ずデポに滞在しなければならない。利益付き配送計画問題の枠組みで研究されている問題としては:
チームオリエンテーリング問題(The Team Orienteering Problem: TOP)が VRPP の変種問題として最も研究されている[4][5][6]。
容量制約付きチームオリエンテーリング問題(The Capacitated Team Orienteering Problem: CTOP)
時間枠付きチームオリエンテーリング問題(The TOP with Time Windows: TOPTW)
集配送計画問題(積み込み・積み降ろし型配送計画問題[7]、Vehicle Routing Problem with Pickup and Delivery: VRPPD): それぞれが独立した集送地と配送地を持った複数の荷物があり、これらの集配送を行う。目標としては集配送を行う地点を巡る中で最適な各車両の配送経路を求めることである。
LIFO付き配送計画問題(Vehicle Routing Problem with LIFO): 集配送計画問題(VRPPD)と類似した問題であるが、車両の積載に関する追加の制約が課される。これは任意の配達地点において配達される荷物は直近に積み込まれた荷物に限定されるという条件である。この条件により、配達すべき荷物以外のものを一時的に降ろす必要がなくなるため、配達地点での積み下ろしの時間が短縮される。
時間枠付き配送計画問題(Vehicle Routing Problem with Time Windows: VRPTW)[8]: 配達場所ごとに配達(あるいは訪問)が可能な時刻(時間枠)が設けられた問題。
^ abcdefghijklToth, P.; Vigo, D., eds (2002). The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. 9. Philadelphia: Society for Industrial and Applied Mathematics. ISBN0-89871-579-2
^Chao, I-Ming; Golden, Bruce L; Wasil, Edward A (1996). “The Team Orienteering Problem”. European Journal of Operational Research88 (3): 464–474. doi:10.1016/0377-2217(94)00289-4.
^Archetti, C.; Sperenza, G.; Vigo, D. (2014). “Vehicle routing problems with profits”. In Toth, P.; Vigo, D.. Vehicle Routing: Problems, Methods, and Applications (Second ed.). pp. 273–297. doi:10.1137/1.9781611973594.ch10
^Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2020). “A hybrid adaptive large neighborhood search heuristic for the team orienteering problem”. Computers & Operations Research123: 105034. doi:10.1016/j.cor.2020.105034.
^Mahmud, Nafix; Haque, Md. Mokammel (February 2019). Solving Multiple Depot Vehicle Routing Problem (MDVRP) using Genetic Algorithm. 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE). doi:10.1109/ECACE.2019.8679429。
^Pavlikov, K.; Petersen, N. C.; Sørensen, J. L. (2023). “Exact Separation of the Rounded Capacity Inequalities for the CapacitatedVehicle Routing Problem”. Networks (Networks) 83: 197–209. doi:10.1002/net.22183.
^Miller, C. E.; Tucker, E. W.; Zemlin, R. A. (1960). “Integer Programming Formulations and Travelling Salesman Problems”. J. ACM7: 326–329. doi:10.1145/321043.321046.
^Christofides, N.; Mingozzi, A.; Toth, P. (1979). The Vehicle Routing Problem. Chichester, UK: Wiley. pp. 315–338
Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). “A hybrid search method for the vehicle routing problem with time windows”. Annals of Operations Research180: 125–144. doi:10.1007/s10479-008-0487-y.
Frazzoli, E.; Bullo, F. (2004). “Decentralized algorithms for vehicle routing in a stochastic time-varying environment”. 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601). 4. IEEE. pp. 3357–3363. doi:10.1109/CDC.2004.1429220. ISBN0-7803-8682-5. ISSN0191-2216
Bertsimas, D.J.; Van Ryzin, G. (1991). “A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane”. Operations Research39 (4): 601–615. doi:10.1287/opre.39.4.601. hdl:1721.1/2353. JSTOR171167.
Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity". arXiv:1903.06322 [quant-ph]。
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの配送計画問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。
Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。