物流配送环节中车辆路径问题(VRP)的研究

山东师范大学

硕士学位论文

物流配送环节中车辆路径问题（VRP）的研究

姓名：史玉敏

申请学位级别：硕士

专业：管理科学与工程

指导教师：赵庆祯

20070410山东师范大学硕士学位论文

物流配送环节中车辆路径问题（ＶＲＰ）的研究

摘要

随着人类社会的发展，对问题的求解要求已经不仅仅停留在可行性的角度上，而是朝

着简洁、高效、快速的方向前进，不仅要求满足人们的生活学习的一般需求，而且在时间、

空间等资源消耗上也要求达到最少，以最小的代价实现最好的结果。现代的物流管理学便

是其中一个例子。随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来

越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的５０％左

右，所以降低物流成本首先要从降低物流配送的运输成本开始。其中，运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。

高节奏高效率的社会，人们对于物品的配送，不仅要满足正常的物品配送要求，而且还在

物质资源、人力资源、时间资源等的消耗上也提出了要求。

在物流配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送

企业提高服务质量、降低物流成本、增加经济效益的影响也较大。而且，随着市场经济条

件下对配送服务水平要求的提高，时间因素在配送过程中越发显得重要。鉴于此，本文将

着重研究带时问窗约束的物流配送车辆路径问题。

运输问题是物流决策中的关键问题。一般来说，除去产品中的采购成本外，运输成本

比任何其他物流活动的成本所占的比例都要高。尽管运输的形式有很多种，但其中最重要

的不外乎运输方式的选择、车辆调度与规划等内容。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对

物流环节的满意度，降低服务商运作成本。正是有这种迫切的需求，所以在计算机高度发展的今天，如何让计算机模拟物流的配送过程，并最终给出最简洁最高效的配送方案，一

直以来是众多计算机学者研究的焦点，并由此衍生出了一个新的研究课题——车辆路径阔

胚（ＶｅｈｉｃｌｅＲｏｕｔｉｆｌｇＰｒｏｂｌｅｍ’ＶＩ｛Ｐ）。

通过世界各国广大研究人员的共同努力，现己提出了许多用于求解不同类型的ＶＲＰ的最优解和近优解的模型及其精确和启发式算法，以及相应的软件包。与国际上相比，国

内对ＶＲＰ的研究相对较少，有关车辆路径问题的研究是在２０世纪９０年代以后才逐渐兴起

的。比国外相对落后３０余年。目前，国内对于复杂的车辆路径问题的研究尚处于起步状

态。

基于对目前ｖＲＰ研究中存在的问题进行详细的分析，本文首先将物流配送问题及物流

配送环节中的ＶＲＰ问题进行系统详细的阐述，包括对该问题提出的研究背景、国内外的研究现状，以及研究的理论依据及存在的问题均作出深刻剖析和总结，并将在ｖＲＰ问题中需

要考虑的目标及约束进行综合，列出一个统一的数学模型。这个模型可以根据不同单位对

各目标的重视程度给每个目标辅以不同的权重值，或者可以将五个目标按优先权合理安排山东师丽犬擘硕士譬位论文目标模型。本文还根据研究该问题的发展过程，把国内外出现的解决ＶＲＰ问题的各种算法

的原理及执行过程作了详细地说明，并分析各种算法的优缺点，说明其最适用于解决何种

问题。然后根据建立的数学模型，找一个典型的物流配送案例，使用ｃ—ｗ方法解决该问

题。最后，对该研究领域做出总结和展望。

关键词：物流物流配送车辆路径问题启发式算法优化

Ｉｌ山东师范大学硕士学位论文

ＲｅｓｅａｒｃｈｏｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓｉｎＬｏｇｉｓｔｉｃｓＤｉｓｔｒｉｂｕｔｉｏｎ

Ａｂｓｔｒａｃｔ

Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｔｈｅｈｕｍａｎｓｏｃｉｅｔｙ，ｔｈｅｓｏｌｕｔｉｏｎｏｆｔｈｅｑｕｅｓｔｉｏｎａｌｒｅａｄｙｎｏｔ

ｍｅｒｅｌｙｐａｕｓｅｓｉｎｔｈｅｆｅａｓｉｂｌｅａｎｇｌｅ，ｂｕｔｆａｃｅｓｔｈｅｄｉｒｅｃｔｉｏｎｔｏｂｅｉｎｇｓｕｃｃｉｎｃｔ，ｈｉｇｈｌｙｅｆｆｅｃｔｉｖｅａｎｄｆａｓｔａｄｖａｎｃｅｄ，ｎｏｔｏｎｌｙｒｅｑｕｅｓｔｓｔｏｈａｖｅｔｏｍｅｅｔｐｅｏｐｌｅ’ｓｇｅｎｅｒａｌｎｅｅｄｉｎｌｉｆｅａｎｄｓｔｕｄｙ，ｂｕｔａｌｓｏｒｅｑｕｅｓｔｓｔｏｃ４】ｎｓａｍｅｔｈｅｌｅａｓｔｒｅｓｏｕｒｃｅｓｏｆｔｉｍｅａｎｄｓｐａｃｅ，ａｃｈｉｅｖｅｓｔｈｅｂｅｓｔｒｅｓｕｌｔｂｙｔｈｅｍｉｎｉｎｌｕｌｎｐｒｉｃｅ．Ｔｈｅｍｏｄｅｍｒｅｓｅａｒｃｈｏｆｔｈｅｌｏｇｉｃｓｍａｎａｇｅｍｅｎｔｉｓａｌｉｅｘａｍｐｌｅ．

Ａｌｏｎｇｗｉｔｈｔｈｅｌｏｇｉｓｔｉｃｓｉｎｄｕｓｔｒｙｄｅｖｅｌｏｐｓｔｏｔｈｅｇｌｏｂａｌｉｚａｔｉｏｎ，ｔｈｅｉｎｆｏｒｍａｔｉｏｎａｎｄｔｈｅ

ｉｎｔｅｇｒａｔｅｄ，ｔｈｅｆｕｎｃｔｉｏｎｏｆｔｈｅｄｅｌｉｖｅｒｉｎｇｉｎｔｈｅｅｎｔｉｒｅｌｏｇｉｓｔｉｃｓｙｓｔｅｍｂｅｃｏｍｅｍｏｒｅａｎｄｍｏｒｅ

ｉｍｐｏｒｔａｍ，Ｔｈｅｔｒａｎｓｐｏｒｔｉｎｇｓｙｓｔｅｍｉｓｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｓｕｂ－ｓｙｓｔｅｍｉｎｔｈｅｄｅｌｉｖｅｒｉｎｇｓｙｓｔｅｍ，ｔｈｅｔｒａｎｓｐｏｒｔｉｎｇｅｘｐｅｎｓｅｏｃｃｕｐｉｅｓａｂｏｕｔ５０％ｉｎｔｈｅｗｈｏｌｅｅｘｐｅｎｓｅ，ａｎｄｔｈｅｒｅｆｏｒｅｉｆｗｅｗａｎｔｔｏ

ｒｅｄｕｃｅｔｈｅｌｏｇｉｓｔｉｃｓ’ｃｏｓｔ，ｗｅｓｈｏｕｌｄｆｉｒｓｔｔｏｒｅｄｕｃｅｔｈｅｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔ．Ａｍｏｎｇｔｈｅｍ，ｗｈｅｔｈｅｒｔｈｅｔｒａｎｓｐｏｒｔｓ’ｌｉｎｅｒｅａｓｏｎａｂｌｅｄｉｒｅｃｔｌｙｉｎｆｌｕｅｎｃｅｓｔｈｅｓｐｅｅｄ，ｔｈｅｃｏｓｔａｎｄｔｈｅｂｅｎｅｆｉｔ，

ｅｓｐｅｃｉａｌｌｙｔｈｅｄｅｔｅｒｍｉｎａｔｉｏｎｏｆｔｈｅｍｕｌｔｉ·ｕｓｅｒｓ’ｄｅｌｉｖｅｒｉｎｇｌｉｎｅｉｓａｃｏｍｐｌｅｘｅｎｇｉｎｅｅｒｉｎｇｓｙｓｔｅｍ．Ｉｎｈｉｇｈ；ｙｒｈｙｔｈｍａｎｄｅｆｆｉｃｉｅｎｃｙｓｏｃｉｅｔｙ，ｔｈｅｇｏｏｄｓｄｅｌｉｖｅｒｉｎｇｎｏｔｏｎｌｙｍｕｓｔｓａｒｉｓｒｙｔｈｅｒｅｑｕｅｓｔｏｆｔｈｅｎｏｒｍａｌｇｏｏｄｓｄｅｌｉｖｅｆｉｎｇ．ｂｕｔａｌｓｏｎｅｅｄｔｏ００ｕｓＬｌｍｅｔｈｅｌｅａｓｔｍａｔｅｒｉａｌｒｅｓｏｕｒｃｅｓ．ｔｈｅ

ｈｕｍａｎＩｆｅｓｏｕｒｃｅｓ，ｔｈｅｔｉｍｅｒｅｓｏｕｒｃｅｓａｎｄｓｏＯｉｌ．Ｉｎｔｈｅｌｏｇｉｓｔｉｃｓｄｅｌｉｖｅｒｉｎｇ，ｔｈｅｖｅｈｉｃｌｅｍｕｔｉｎｇｐｒｏｂｌｅｍａｆｆｅｃｔｓｂｒｏａｄｌｙａｒｅａ，ａｎｄｎｅｅｄｓｔｏ

ｃｏｎｓｉｄｅｒａｌｏｔｏｆｆａｃｔｏｒｓ，ｔｈｅｉｎｆｌｕｅｎｃｅｔｏｔｈｅｅｎｔｅｒｐｒｉｓｅｔｏｉｍｐｒｏｖｅｔｈｅｇｒａｄｅｏｆｓｅｒｖｉｃｅ，ｔｏ

ｒｅｄｕｃｅｔｈｅｃｏｓｔｏｆｔｈｅｌｏｇｉｓｔｉｃｓ，ｔｏＩｎｃｒｅａｓｅｅｃｏｎｏｍｉｃｓ’ｅｆｆｉｃｉｅｎｃｙｉｓｂｉｇ．Ｂｅｃａｕｓｅｔｈｅ

ｅｎｈａｎｃｅｍｅｎｔｏｆｔｈｅｍｑｕｅｓｔｏｆｄｅｌｉｖｅｒｉｎｇｓｅｒｖｉｃｅＩｎｔｈｅｍａｒｋｅｔｅｃｏｎｏｍｙ。ｔｈｅｔｉｍｅｆａｃｔｏｒｉｎｔｈｅ

ｄｅｌｉｖｅｒｉｎｇｐｒｏｃｅｓｓｂｅｃｏｍｅｍｏｒｅａｎｄｍｏｒｅｉｍｐｏｒｔａｎｔ．Ｉｎｖｉｅｗｏｆｔｈｉｓ，ｔｈｉｓａｒｔｉｃｌｅｗｉｌｌ

ｅｍｐｈａｔｉｃａｌｌｙｓｔｕｄｙｔｈｅｖｅｈｉｃｌｅｍｕｔｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｉｍｅｗｉｎｄｏｗｓ．Ｔｈｅｄｅｌｉｖｅｒｉｎｇｐｒｏｂｌｅｍｉｓｔｈｅｋｅｙｉｎｔｈｅｌｏｇｉｓｔｉｃｓ’ｐｏｌｉｃｙ－ｍａｋｉｎｇ，Ｇｅｎｅｒａｌｌｙｓｐｅａｋｉｎｇ，

ｅｘｃｅｐｔｏｕｔｓｉｄｅｔｈｅｐｒｏｄｕｃｔ’ｓｃｏｓｔｉｎｐｕｒｃｈａｓｅ，ｔｈｅｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔｏｃｃｕｐｉｅｓｈｉｇｈｅｒｐｒｏｐｏｒｔｉｏｎ

ｔｈａｎａｎｙｏｔｈｅｒｔｈｉｎｇｓ．Ａｌｔｈｏｕｇｈｔｈｅｒｅａｒｅｍａｎｙｋｉｎｄｓｏｆｔｒａｎｓｐｏｒｔａｔｉｏｎｆｏｒｍｓ，ｔｈｅｍｏｓｔ

ｉｍｐｏｒｔａｎｔｔｈｉｎｇｓａｔｅｔｒａｎｓｐｏｒｔａｔｉｏｎ’ｓｍｏｄｅｃｈｏｏｓｉｎｇ、ｖｅｈｉｃｌｅｓｄｉｓｐａｔｃｈｉｎｇａｎｄｐｌⅢ－ｍｉｎｇａｎｄ∞

ｏｎ．

Ｓｅｌｅｃｔｉｎｇｔｈｅａｐｐｒｏｐｒｉａｔｅｖｅｈｉｃｌｅｒｏｕｔｉｎｇｍａｙｓｐｅｅｄｕｐｔｈｅｒｅｓｐｏｎｓｅｔｏｔｈｅｃｕｓｔｏｍｅｒｓ’

ｄｅｍａｎｄ．ｉｍｐｒｏｖｅｔｈｅｇｒａｄｅｏｆｓｅｒｖｉｃｅ，ｅｎｈａｎｃｅｔｈｅｄｅｇｒｅｅｏｆｃｕｓｔｏｍｅｒｓ’ｓａｔｉｓｆａｃｔｉｏｎ，ｒｅｄｕｃｅｔｈｅｓｅｒｖｉｃｅｂｕｓｉｎｅｓｓｏｐｅｒａｔｉｏｎ’ｓｃｏｓｔ．Ａｃｃｏｒｄｉｎｇｔｏｓｕｃｈａｋｉｎｄｏｆｕｒｇｅｎｔｄｅｍａｎｄ，ｉｎｔｈｅ

ｃｏｍｐｕｔｅｒｓ’ｈｉｇｈｌｙｄｅｖｅｌｏｐｉｎｇｄａｙ，ｈｏｗｔｏｌｅｔｔｈｅｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｅｔｈｅｐｒｏｃｅｓｓｏｆｌｏｇｉｓｔｉｃｓｄｅｌｉｖｔ，ｎＳｎｇ，ａｎｄｆｉｎａｌｌｙｐｒｏｄｕｃｅｓｔｈｅｍｏｓｔｓｕｃｃｉｎｃｔｌｙａｎｄｈｉｇｈｌｙｅｆｆｅｃｔｉｖｅｄｅｌｉｖｅｒｉｎｇｐｌ札ｈａｓ

ⅡＩ山东师范大学硕士学位论义ｓｉｎｃｅａｌｗａｙｓｂｅｅｎａｆｏｃａｌｐｏｉｎｔｗｈｉｃｈｔｈｅｍｕｌｔｉｔｕｄｉｎｏｕｓｃｏｍｐｕｔｅｒｓｃｈｏｌａｒｓｔｕｄｙ，ａｎｄｆｒｏｍｔｈｉｓ

ｇｒｏｗｓａｎｅｗｒｅｓｅａｒｃｈｔ叩ｉｃ－一ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓ，ＶＲＢ

Ｔｈｒｏｕｇｈｔｈｅｖａｒｉｏｕｓｃｏｕｎｔｒｉｅｓｇｅｎｅｒａｌｒｅｓｅａｒｃｈｅｒ＇ｓｊｏｉｎｔｅｆｆｏｒｔ，ａｌｒｅａｄｙｈａｖｅｐｒｏｐｏｓｅｄ

ｍａｎｙｔｙｐｅｏｆｏｐｔｉｍａｌｓｏｌｍｉｏｎａｎｄｔｈｅｎｅａｒｓｕｐｅｒｉｏｒｓｏｌｕｔｉｏｎｍｏｄｅｌａｎｄｉｔｓｉｍｐｒｅｃｉｓｅａｎｄｔｈｅ

ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅｄｉｆｆｅｒｅｎｔｔｙｐｅｏｆｔｈｅＶＲＰ．ａｓｗｅｌｌａｓｃｏｒｒｅｓｐｏｎｄｉｎｇｓｏｆｔｗａｒｅ

ｐａｃｋａｇｅ．Ｃｏｍｐａｒｅｄｗｉｔｌｌｔｈｅｉｎｔｅｒｎａｔｉｏｎａｌ，ｄｏｍｅｓｔｉｃ’ｓＶＲＰｒｅｓｅａｒｃｈｉｓｌａｔｅｒ，ｏｎｌｙｇｒａｄｕａｌｌｙ

ｅｍｅｒｇｅｓｉｎｔｈｅｌ９９０ｓ，ｃｏｍｐａｒｅｄｔｏｏｖｅｒｓｅａｓｒｅｌａｔｉｖｅｌｙｆａｌｌｂｅｈｉｎｄｆｏｒｍｏｒｅｔｈａｎ３０ｙｅａｒｓ．ＡｔｐｒｅｓｅｎＬｄｏｍｅｓｔｉｃ’ｓｃｏｍｐｌｅｘｖｅｈｉｃｌｅｍｕｔｉｎｇｐｒｏｂｌｅｍｒｅｓｅａｒｃｈｉｓｏｎｌｙｓｔａｒｔｅｄ．ＢａｓｅｄｏｉｌｔｈｅａｎａｌｙｚｅｓｔｏｔｈｅｑｕｅｓｔｉｏｎｗｈｉｃｈｅｘｉｓｔｓｉｎｔｈｅｐｒｅｓｅｎｔＶＲＰｒｅｓｅａｒｃｈｉｎｄｅｔａｉｌ，ｔｈｉｓａｒｔｉｃｌｅｆｉｒｓｔｅｌａｂｏｒａｔｅｓｔｈｅｌｏｇｉｓｔｉｃｓｄｅｌｉｖｅｒｉｎｇｐｒｏｂｌｅｍａｎｄｔｈｅｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｉｎ

ｔｈｅｌｉｎｋｏｆｔｈｅｌｏｇｉｓｔｉｅｓｄｅｌｉｖｅｒｉｎｇｐｒｏｂｌｅｍｉｎｄｅｔａｉｌ，ｉｎｃｌｕｄｉｎｇｒｅｓｅａｒｃｈｉｎｇｈａｅｋｇｒｏｕｎｄ，ｄｏｍｅｓｔｉｃ’ｓａｎｄｉｎｔｅｒｎａｔｉｏｎａｌ’ｓｐｒｅｓｅｎｔｒｅｓｅａｒｃｈｉｎｇｓｉｔｕａｔｉｏｎｗｈｉｃｈｐｒｏｐｏｓｅｓｔｏｔｈｉｓｑｕｅｓｔｉｏｎ，∞ｗｅｌｌａｓｔｈｅｒｅｓｅｍｅｈｔｈｅｏｒｙ’ｓｂａｓｉｓａｎｄｔｈｅｅｘｉｓｔｅｎｃｅｑｕｅｓｔｉｏｎｗｉｌｌｍａｋｅｔｈｅｐｒｏｆｏｕｎｄａｎａｌｙｓｉｓａｎｄｔｈｅｓｍａｒｎａｌｙ．Ａｎｄｌｉｓｔａｕｎｉｆｉｃｄｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌａｃｃｏｒｄｉｎｇｔｏｔｈｅｇｏａｌａｎｄｔｈｅｒｅｓｔｒａｉｎｔ．ｗｈｉｃｈｗｉｌｌｎｅｅｄｔｏｃｏｎｓｉｄｅｒｉｎｔｈｅⅥ冲，Ｔｌｌｉｓｍｏｄｅｌｍａｙａｃｔａｃｃｏｒｄｉｎｇｔｏｖａｒｉｏｕｓｇｏａｌｓｖａｌｕｅ