供应链中车辆路径问题的研究进展及前景

摘要/Abstract

摘要： 车辆路径问题是供应链研究的一项重要内容。本文概述了近年来车辆路径问题研究的现状；介绍了车辆路径问题主要的几种分类方法；总结了车辆路径问题中几种常见的附加条件。分别介绍了确定车辆路径问题、随机车辆路径问题和模糊车辆路径问题出现的背景及其具体应用场合，讨论并总结了针对这些问题的不同建模方法和算法求解思路，以及这些算法的优点、局限和适用范围。简要介绍了国内该领域的发展现状，并结合供应链应用的需要，指出车辆路径问题的研究发展方向。

关键词: 确定性, 车辆路径问题, 非确定性车辆路径问题, 供应链

Abstract: Vehicle routing problem is an important content in supply chain field. This paper gives a review of achievements of vehicle routing problem. Several category methods are introduced, and quite a few common side conditions are summarized. Backgrounds and detail application fields for deterministic VRP, stochastic VRP and fuzzy VRP are introduced, different model methods for them are discussed, diverse algorithm ideas for them are summarized, and the advantage and limitation for these algorithm are discussed, furthermore, their applicable cope are also presented. On the other hand, brief summarization for home study is also presented. The further efforts are presented, while demand for application of supply chain is combined.

Key words: certain, vehicle routing problem , uncertain rehicle routing problem, supply chain

中图分类号:

TP14

祝崇隽，刘民，吴澄. 供应链中车辆路径问题的研究进展及前景[J]. .

ZHU Chong-jun, LIU Min, WU Cheng. Review of Vehicle Routing Problem in Supply Chain[J]. .

参考文献

［1］DANTZIG G, RAMSER J. The truck dispatching problem［J］. Management Science, 1959, (6): 80-91.

[2]LAPORTE G. The vehicle routing problem: An overview of exact and approximate algorithms［J］. European Journal of Operational Research, 1992, 59: 345-358.

[3]LAPORTE G, MERCURE H, NOBERT Y. An exact algorithm for the asymmetrical capacitated vehicle routing problem［J］. Networks, 1986,16: 33-46.

[4]CHRISTOFIDES N, MINGOZZI A, TOTH P. Exact algorithms for the vehicle routing problem, based on spanning the shortest path relaxation［J］. Mathematical Programming, 1981, 20: 255-282.

[5]FISHER M L. Optimal solution of vehicle routing problems using minimum k-trees［J］. Operations Research, 1994, 42 (4) : 626-642.

[6]EILON S, WATSON-GANDY C D T, CHRISTOFIDES N. Distribution management: mathematical modelling and practical analysis［M］. London: Griffin，1971.

[7]BALINSKI M, QUANDT R. On an integer program for a delivery problem［J］. Operations Research, 1962, 12: 300-304.

[8]RAO M R, ZIONT S. Allocation of transportation units to alternative trips- A column generation scheme with out-of-kilter subproblems［J］. Operations Research, 1968, 12: 52-63.
[9]FISHER M L, JAIKUMAR R. A generalized assignment heuristic for vehicle routing［J］. Networks, 1981, 11: 109-124.
[10]LAPORTE G, NOBERT Y, DESROCHER M.Optimal routing under capacity and distance restritions［J］. Operations Research, 1985, 33: 1050-1073.

[11]CLARKE G, WRIGHT J W.Scheduling of vehicles from a central depot to a number of delivery points［J］. Operations Research, 1964, 12: 568-581.

[12]PAESSENS H. The saving algorithm for the vehicle routing problem［J］. European Journal of Operational Research, 1988, 34: 336-344.

[13]GILLETT B, MILLER L. A heuristic algorithm for the vehicle dispatch problem［J］. Operations Research, 1974, 22: 340-349.

[14]CHRISTOFIDES N, MINGOZZI A, TOTH P.Cominatorial Optimization［M］. Wiley, Chichester, 1979.

[15]GENDREAU M, HERTZ A， LAPORTE G. A tabu search heuristic for the vehicle routing problem［M］. Montreal:Publication #777, Centre de recherche sur les transpors, 1991.

[16]TAILLARD E. Parallel interative search method for vehicle routing problems［J］. Networks, 1993, 23: 661-673.

[17]LAWRENCE S，MOHAMMAD A. Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem［A］. Proceedings - Annual Meeting of the Decision Sciences Institute［C］. Decis Sci Inst.1996.488-490.

[18]NICOLAS B, PASCAL B. Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques［A］. Proceedings of the IEEE Conference on Evolutionary Computation［C］. 1998.

[19]张涛，王梦光.遗传算法和3-OPT结合求解带能力约束的VRP［J］.东北大学学报，1999, 20(3): 253-256.

[20]WARK P, HOLT J. A repeated matching heuristic f

[1]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[2]	张念,李会鹏,蹇洁,苏加福. 价格折扣下后悔预期对供应链成员企业定价决策的影响[J]. 计算机集成制造系统, 2021, 27(8): 2437-2447.
[3]	李绩才,刘燕飞,楼婷渊,李昌文,周永务. 带有网络直销的双渠道制造商供应链中的定价和广告决策[J]. 计算机集成制造系统, 2021, 27(8): 2448-2460.
[4]	谭春桥,李波,周丽. 考虑企业社会责任的物流服务供应链定价决策[J]. 计算机集成制造系统, 2021, 27(8): 2461-2475.
[5]	董景峰,高珊,高贵晨,杨若怡. 顾客感知价值和回收质量不确定下的闭环供应链定价决策[J]. 计算机集成制造系统, 2021, 27(8): 2476-2490.
[6]	张雪梅,周根贵,曹柬. 考虑政府规制和供应链协调的再制造微分博弈模型[J]. 计算机集成制造系统, 2021, 27(7): 2095-2111.
[7]	郭羽含,于俊宇,刘万军,张宇,张美琪. 制造业可持续供应链网络建模及求解[J]. 计算机集成制造系统, 2021, 27(7): 2112-2133.
[8]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[9]	胡盛强,程硕,王新林. 考虑产出随机的采购策略选择与供应链协调[J]. 计算机集成制造系统, 2021, 27(7): 2156-2170.
[10]	孙晋怡,周岩,曲箫宇. 考虑质量和延保服务的多产品供应链网络均衡[J]. 计算机集成制造系统, 2021, 27(6): 1833-1842.
[11]	何丽娜,王国涛,刘珏. 基于犹豫模糊DEMATEL与风险屋的供应链风险管理[J]. 计算机集成制造系统, 2021, 27(5): 1459-1468.
[12]	戚佛兰,周岩. 考虑渠道公平的双渠道二层供应链网络均衡策略[J]. 计算机集成制造系统, 2021, 27(5): 1469-1482.
[13]	王忠伟,尹谦,庞燕,邢立宁,任腾. 再制造闭环供应链回收问题研究进展[J]. 计算机集成制造系统, 2021, 27(4): 1201-1210.
[14]	蔡建湖,张玉洁,徐芳,黄卫来. 交货时间不确定环境下两级供应链库存决策与契约设计[J]. 计算机集成制造系统, 2021, 27(4): 1211-1225.
[15]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.