毕业论文 基于节约法鲜奶配送车辆调度优化研究

1、 本科生毕业论文（设计）题 目:基于节约法鲜奶配送车辆调度优化研究 目 录摘要1关键词：1Key words:11 绪论11.1课题背景11.2 研究意义21.3 国内外研究状况22 鲜奶配送车辆调度问题概述22.1 车辆调度优化问题的概述22.2 车辆调度问题的构成要素32.3 鲜奶配送的一般过程33 节约算法介绍43.1节约算法的基本原理43.2 节约算法制定配送计划的步骤54 鲜奶配送车辆路径模型的建立64.1 优化目标和约束条件的确定64.2 约束条件的确定74.2.1 车辆载重和容量的约束74.2.2时间窗的约束74.3 模型的建立75 算例分析85.1 算例数据85.2结果分析9致

2、谢9参考文献：10基于节约算法的鲜奶配送车辆调度优化研究物流工程专业学生 陆辉指导教师 朱国宗摘要：二十一世纪是经济全球化的时代，伴随着市场经济的不断深入发展，鲜奶企业将面对更加激烈的市场竞争。合理化的安排鲜奶配送路径降低企业成本提高鲜奶配送效率成为了鲜奶企业提升企业竞争力的有力手段。本文通过运用节约算法，建立鲜奶配送数学模型，找出最优化配送路径。关键词：物流配送；节约算法；车辆调度；路线优化Saving algorithm based on Vehicle Scheduling ProblemStudent majoring in Logistics

3、Engineering Lu Hui Tutor Zhu GuozongAbstract：The twenty-first century is the era of economic globalization, along with the deepening of market economy development, and milk enterprises will face more intense competition in the market. Milk distribution route rationalization arrangements reduce the c

4、ost of improving the efficiency of milk into a milk distribution business to enhance the competitiveness of enterprises a powerful tool. Through the use of saving algorithm, the establishment of milk distribution model, to identify the most optimal distribution path.朗读显示对应的拉丁字符的拼音字典Key words: Logist

5、ics and distribution；CW；Vehicle Scheduling; Route Optimization；1 绪论 1.1课题背景进入新世纪以后，随着科学技术的进步，经济全球化发展，国际贸易的内容、形式正发生着深刻的变化。技术贸易、服务贸易在国际贸易中比重在不断增加，跨国连锁经营风霏全球。尤其2001年我国正式加入WTO后，国内市场更加开放，境外资金和企业大量涌进，国内企业和贸易面临更加激烈和残酷竞争(ComPetition)。为了提高竞争力，国内企业，尤其是与国际贸易有着密切关系的企业，纷纷吸收国外许多先进的制造技术和管理方法。其中，物流配送及车辆调度优化倍受世人关注。随

6、着人们的生活水平的不断提高，奶制品已成为了人们的日常消费品，在“一杯牛奶强壮一个民族“的口号下奶制品市场有了一个空前旺盛的发展。而鲜奶产业是其产品具有储存期限短，国家对其的保鲜标准要求高，整个生产流程要达到“当日生产，当日加工，当日销售”特珠要求的产业，因此，从物流配送过程中对于鲜奶的配送有着严格的时间上的要求，对于鲜奶的保鲜起到了一个很大的影响。本文将试图结合鲜奶产品的特点，从鲜奶配送车辆行驶路径的科学化着手，通过节约算法解决鲜奶配送过程中配送中心与订奶销售点之间车辆的一般调度问题，分析出鲜奶配送车辆调度问题的影响因素，并找出最优化的车辆路径优化方法，来帮助提高鲜奶企业的竞争力。1.2 研究

7、意义在市场竞争日益激烈的条件下，重视与加强鲜奶配送流程优化的研究，对于企业生存和发展而言，具有深远意思。从长期的角度来看，合理的配送流程不仅能使企业的产品和服务高效地传递到消费者中，而且还能促进企业的持续发展。企业必须对现在的配送环节调整优化，建立符合自身的配送流程，企业才能真正得以生存和发展。合理的配送流程有助于企业降低成本，提高经济效益，有助于企业建立自己的竞争优势，只有深入研究企业的配送流程，将企业生产技术和管理、营销网络、仓储等企业资源加以统筹整合，形成企业自身独特的优势，才能真正的提高企业竞争力。1.3 国内外研究状况车辆调度问题最早是由Dantzig和Ramsert在上个世纪50年

8、代末期提出，该问题一般称之为Vehicle Routing Problem(VRP)或者Vehicle Scheduling Problem(VSP)，现在我们将车辆调度问题一律简称为VRP。 VRP提出后就很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科的专家对该问题进行了大量的理论研究及实验分析，取得了很大进展。国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立

9、了最简单的VRP模型；1964年，Clarke和Wright提出了一种启发式节约法来建立车队配送路线；1968年，Rao等人在VRP 集分割的基础上引入了列生成方法进行求解，这种算法本质上是最短路径算法，同时结合了分枝定界算法；1971年，Eilon 等人提出将动态规划法用于固定车辆数的VRP，通过递归方法求解；1981年，针对带能力约束、时间窗以及无停留时间的VRP，Fisher提出了三下标车辆流方程；Thangiah于1991和Joe于l993分别用遗传算法求解VRP，但是都存在“早熟收敛”的问题；2001年，Tan，Lee，Du结合遗传算法、tabu树搜索算法的优点，形成知识库，用人工智

10、能的方法来求解；2002年，Taranrilis,Kiranondis使用空间决策支持系统来解决车辆路径问题。在国内,有关车辆调度问题的研究是在20世纪90年代以后才逐渐兴起的，比国外相对落后。国内研究对象主要是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem，简称CPP)、有向中国邮递员问题(DirectedChinese Postman Problem，简称DCPP)等，系统性研究还很少见到。西南交通大学的李军教授和郭耀煌教授对车辆优化调度的基础理论及各类问题进行了系统的研究；李大为等以TSP的最

11、近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VRP。另外在利用现代优化算法(如:遗传算法、神经网络方法、模拟退火等)对简单TSP的求解取得了一定成果。蔡延光等应用模拟退火法针对满载问题进行了求解。总体来说，目前我国对车辆调度问题的理论研究仍相对薄弱，需要进一步研究。2 鲜奶配送车辆调度问题概述 2.1 车辆调度优化问题的概述物流配送车辆调度优化问题可以看成：在一个存在供求广西的系统中，有若干台车辆、若干个配送中心和客户，要求合理安排车辆路线和出行时间，从而在给定的约束条件下，把客户需求的货物从配送中心送到客户，并使目标函数取得优化。物流配送车辆调度优化问题最早是由Dent

12、zing和Ramser在1959年第一次提出的。从此，车辆调度优化问题很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者的极大重视，同时也逐渐成为运筹学与组合优化领域的热点研究问题。由于它应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。国外将物流配送车辆优化调度问题归结为或称之为Vehicle Routing Problem和Vehicle Scheduling Problem。物流配送车辆调度问题一般研究的是在配送中心及用户位置均已知、资源及运输能力充分、各用户需求量己知的前提下，如何合理、高效、低成本的解决分配与运送的问题，也

13、就是说如何将货物从配送中心按照一定的要求发送到若干个用户点。配送方案应该包括两个相关的环节： 有哪些用户要被分配到一条回路上，即有哪些用户的货物应该安排在同一辆车上； 每条配送路线上用户的连接顺序。物流配送车辆调度的最优解实际上是一个效率最高的运输方案，它应明确的规定应派出的车辆型号、车辆数以及每辆车的具体行车路线。实施这一配送方案，即可以满足用户的需求，又可以使总的运输行程最短。2.2 车辆调度问题的构成要素物流配送车辆调度问题主要包括货物、车辆、配送中心、客户、约束条件和目标函数等要素。(1)货物货物是我国交通运输领域中的一个特有专用概念，交通运输领域将其经营的对象分为两大类：一类是人，一

14、类是物。“物”这一类的运输目标统称为货物。我们这里所说的货物是指物流配送的对象，每批货物都包括品名、包装、重量、体积、要求送到的时间和地点，能否分批配送等属性。(2)车辆车辆是“车”与车的单位“辆”的总称。所谓车，是指陆地上用轮子转动的交通工具；所谓辆，来源于古代对车的计量方法。本文所说的车辆是指运载货物的工具，车辆的主要属性包括：类型、工作时间、配送前的停放位置、载重量以及配送任务完成后的停放位置等。(3)配送中心配送中心是指接受供应者所提供的多品种、小批量的货物，通过存储、保管、分拣、配货以及流通加工、信息处理等作业后，将按需要者订货要求配齐的货物送交顾客的组织机构和物流设施。本文所说的配

15、送中心是指从事配送业务的物流场所或组织，如可以进行货物集中、分拣、配货、送货等的仓库、车站、港口等固定场所。在物流配送系统中，配送中心可以只有一个，也可以同时具有多个。(4)客户客户指的是物流配送的服务对象，可以是各种零售店，也可以是分仓库，还可以是别的仓库的外调。也就是说客户是有配送任务的对象的统称。客户的属性包括需求数量、需求时间、需求次数及目前需求的满足动态等。(5)约束条件物流配送车辆调度问题应满足以下约束条件：能够满足所有客户对货物品种、规格、数量的要求；能够在客户要求或者承受的时间内将货物送到；运输车辆每天的运行时间、运行历程都要有一定的限制，不能超过预定的时间或者里程；在物流配送

16、过程中实际装载的货物不能超过车辆的最大载重要求，也就是不能超载；当然，客户的需求也必须在物流中心现有的运力范围内，也就是目前有这个能力去完成待完成的任务。(6)目标函数目标函数是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。简单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。2.3 鲜奶配送的一般过程 鲜奶配送是从鲜奶生产出来以后运送的到各个鲜奶配送中心，再由配送中心运到各区的订奶点、超市、零售点和区区域经销商，最后到达消费者的过程。整个配送流程可以整合成如图1所示。图1鲜奶配送流程图3 节约算法

17、介绍3.1节约算法的基本原理节约法可分为两种，一种为时间节约法，即以节约时间为目标；另一种为里程节约法，即以节约总里程为目标，两种节约法的基本原理都是三角形的任意一边的长度必定小于另外两边的长度之和。图2节约法原理图如图2所示，如果配送中心分别向两用户、配送货物，则车辆运行总距离为：如果用一辆车来完成配送，则车辆运行的总距离为：另一种配送法案比前一种配送法案节约距离为：（根据三角形中两边之和大于第三遍原理）。三个用户、的情况如图2所示，、之间无直达路线，如果现在一辆车为、用户配送，所走路线为；另一辆车为用户配送，所走路线为。如果用一辆车为三个用户、一同配送，则车辆所走路线为，此法案比前法案节约

18、距离为：图2 模拟图以此类推，多个用户用一辆车配送，所走过的总路程最短。但是实际配送过程中经常有各种各样的约束条件，如顾客对货物品种、规格和数量的要求；对货物送达时间或者时间范围的要求；道路运行条件对配送车辆的制约，如单行道、通行的限制；车辆容量和载重的限制；还有许多其他制约条件。由此，用户逐渐增多，就产生了多个满足约束条件的线路组合，各个组合产生不同的节约里程。当然，在总里程最小化目标的情况下，应该选择节约里程最大的一个方案，这正是节约法的思想所在。我们所见过的文献中，利用节约法要么以节约时间为目标，要么以节约总里程为目标；两种方法的基本原理都是三角形的一边必定小于另外两边之和。本论文讨论的

19、是以节约综合成本为目标，因此也可以认为是对原始的节约法的拓展和改进。3.2 节约算法制定配送计划的步骤设从流通中心向用户(i=1,2,·····,n)配送商品，(i=1,2,······,m)是从向配送的商品量，与 之间的最短配送距离为 (i, j=0, 1, 2, , m)，发送车辆按其载重(或容量)不同有n种 ，装载量为的发送车有辆( i=1, 2, , n)且和，此式表示总需求远远大于最小的发送车的载重(或容量)。相反，如果，即每一辆发送车的装载量(或者容量)都大于所有用户的总需

20、求量，如果没有其它限制条件，则直接用一辆车送货，问题转化为最短路问题。首先，假定向每一个用户都派出一辆车，且 ，即各用户的需求量都小于最大发送车的运载量。这种做法是最最简单的方案，但是这样做的效率是不高的，只是为了得到一个初始解而已。如果某一用户的需求量大于最大车的载量，则先派整车配送，余下不足整车部分设为需求量，参与节约法分配。s(I,j)是和连在一条线上的节约量，当 i, j1, ij时，节约量 s(i，j)可以按公式计算。如果和连接起来，则，且；如果不连接起来则，且；如果用一辆车就可以给用户送完货，则，且。在这些定义下，可得公式(j=1, 2,m)，从而确保车辆返回配送中心。在初始解的基

21、础上，按以下条件选出最大节约量的对应点，并检验两点是否可以连接。在一条线路上，运用一辆车完成配送：（1），即、与起点或终点相连接，或者说都是线路上的外点；（2）和尚未被分配在相同线路上；（3）将原计划中分别配送 和改为采用装载量为的车辆进行配送，且不超载；如果最大节约量对应点和的情况符合上述条件，则可连接 和，即，其它的值按公式修改，续(4)，否则继续(6)；（4）对于或的 j，使 =0；(5)对于和 的 j，把它所在线路上的货物量加在一起，作为新的 (6)删除 S (i，j)，继续(1)，直到全部 S(i，j)被删除。在进行此项工作时，如果具有最大节约量的对应点对有两组以上，则可以随机选取其

22、一，按上述原则反复进行计算和修改，直到各用户间都进行过连接为止。节约法的计算流程：4 鲜奶配送车辆路径模型的建立4.1 优化目标和约束条件的确定鲜奶配送车辆路径选择最优化研究的是如何使得鲜奶配送的车辆行走的路径最短的问题，也可以把它简单的看成是一辆车从某一点出发，没个点至少经过一次，在最后返回出发点的情况下，使得整个过程的行驶路线最短的问题，在本文的研究中将鲜奶配送车辆路线调度优化的过程中，整体过程的成本的最优化作为第一目标，而时间的最优化可以作为一个参考目标，这些都要给予现实而定，对于所有鲜奶行业而言，其整个系统的成本最小化和鲜奶的新鲜度是企业最有利的竞争力。所以配送车辆路线的合理化对于企业

23、提高收益有至关重要的作用。4.2 约束条件的确定 在现实中鲜奶配送车辆路径和配载的因素主要有以下几点：客户需求时间窗约束、道路交通状况的约束、车辆载重与容量的约束及鲜奶储存条件的约束等。4.2.1 车辆载重和容量的约束鲜奶配送车辆进行配载时，需要考虑配载车辆的额定载重与实际的有效载重，因为客户大多是小货量客户，要求一个客户的鲜奶需求不能被分装在不同的车上，也就是说每个客户的配载必须且只能由一辆回收车辆来负责回收运送，不能被分装。所以，车辆的载重量与货物的分装约束也是需要考虑的。只要鲜奶配送的车辆确定其服务的客户也就确定了，此时相应车辆所走的路线也就确定了，而对路径的选择又使用节约算法进行求解。

24、4.2.2时间窗的约束在现实中，不同的客户对鲜奶配送的时间段不尽相同，而空间距离在客观上也为鲜奶配送在时间上制造了障碍，故而时间窗约束是鲜奶配送过程中车辆调度必须重点考虑的因素之一。假设完成任务i需要的时间表示为Ti，又设任务i的开始时间需在一定的时间范围ETi，LTi内，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟时间。若车辆到达i的时间早于ETi ，则车辆需在i处等待，若车辆到达时间晚于LTi ，则任务i要延迟进行。以Si表示车辆到达i的时间，tij表示车辆由点i行驶到点j的时间，一般有如下关系式：S00 ETiSiLTi一般而言，时间窗分为二种类型：硬时间窗、软时间窗。

25、在对时间窗的选择选择上要根据实际情况分析而定，下面是对二种类型的时间窗进行的详细分析。（1）软时间窗: 软时间窗调度问题是指客户对于货物的到达时间有一点的时间要求，但相对比较宽松，尽量在客户要求的时间限制内完成，但是如果过了客户要求的时间会有一定的惩罚。（2）硬时间窗: 硬时间窗的顾客对于货物的到达时间有着严格的硬性时间限制。4.3 模型的建立进行鲜奶配送车辆的路径问题可以描述为：多车辆对多客户按一定的路径准时的送达，其模型可以描述为：为了方便研究，将配送中心编号为0，任务编号为1，···，k，任务与配送中心表示为点i(i0,1,，k)，则定义变量为：其中：1表示

26、点i的任务车c完成，0表示否则；其中：1表示车辆c从i行驶到j，0表示否则；模型如下： ，k， ，1，k， ，1，k， =0或1 ，1，k，=0或1 ，1，k，模型中，q表示车辆k的额定载重量；ga表示任务a处所需的载重量。5 算例分析5.1 算例数据假设某一个区有10个牛奶订奶点某一天的运输任务（为1,2，······10），各点的需求量为（箱）。要求任务开始时间为5:00。车辆行驶速度45km/h；车辆载重为50（箱）；各个点的点对点距离如表1所示：（km）。表1 各点需求表任务i123456789107589479756时间约束

27、0.5-10.75-10.5-10.75-1.50.75-1.50.5-1.251-1.750-0.80.5-1.50.5-1.75表2 各点相对距离0123456789100011141279158141114111091481723171572021408615161822162531207109192120254701016111813195907102118176150172725267801315881408991101510140计算各点对之间的距离节约量得到各点对之间的距离节约量，按顺序排列如表3所示：表3 距离节约值(i,j)1,21,31,41,51,61,71,81,91,

28、102,32,42,52,62,72,8(I,j)1691033210155181881346(i,j)2,92,103,43,53,63,73,83,93,104,54,64,74,84,94,10(i,j)931211181551664352(i,j)5,65,75,85,95,106,76,86,96,107,87,97,108,98,109,10(i,j)17722662139414171910首先，根据总需求量7+5+8+9+4+7+9+7+5+6=65>50，因此至少需要两辆车来运输任务。根据表3所示的S(i,j)的顺序，逐项考察对应的点对之间的连线。Step 1连接8,10

29、假设路线为0-8-10，则t10=t8+S(8,10)=14/45+9/45=0.31+0.2=0.51在0.5-1.75内，载重符合；假设路线为0-10-8，则t8=t10+S(10,8)=0.75+0.31=0.81>0.8;选0-8-10；Step 2连接2,3假设路线为0-2-3，则t3=t2+S(2,3)=0.75+0.18<1,载重符合；假设路线为0-3-2，则t2=t3+S(3,2)=0.5+0.18<0.75,载重符合；Step 3连接2,4假设路线为0-2-4，则t4=t2+S(2,4)=0.75+0.13=0.88<1.5,载重符合；假设路线为0-4

30、-2，则t2=t4+S(4,2)=1+0.13=1.13>1,选0-2-4；结合2）得；0-3-2-4；Step 4连接3,6由上面可得路线为0-6-3-2-4，则t4=0.5+0.2+0.18+0.13=1.01在0.75,1.5内，载重符合；Step 5连接1,9；8,9结合1）可得路线为0-1-9-8-10，则t10=0.5+0.18+0.31=0.99在0.5-1.75内，载重符合；Step 6 连接5,6；结合(4),而5是内点，可得:路线0-5-6-3-2-4，符合条件；Step 7 连接10,7； 结合(5)，可得:路线0-1-9-8-10-7，符合条件。所以最终满意解，共

31、需两辆车，两条路线分别为：A.0-5-6-3-2-4-0B.0-1-9-8-10-7-05.2结果分析通过以上结果我们可知通过对鲜奶配送车辆路径调度优化能够有效的节约物流成本，掉地企业的运营成本，缩短鲜奶运输时间，提高企业竞争力。在模型中必须准确地确定相应的约束条件，将其归类，逐步解决，在运行模型时要统筹兼顾，全面地分析模型，文中带有时间窗的VSP问题通过运用节约算法在连接前加入相应的约束以检验连接是否可行，从而解决车辆配送的问题，得出满意的配送方案。致谢参考文献：1Lee C G. Vehicle routing and invent or y control for in-bound lo

32、gistics D. The University of Michigan, 2001.2 Dr or M, Trudeau P. Split delivery routing J .Naval Research Logistics, 1990, ( 37) : 383402.3 Altinel I K, et al. A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem J . The Journal of t he Operational Research Society, 2005,56( 8) : 9541012.4 Chandra P, Fisher M L. Coordination o f production and distribution planning J . European Journal of Operational Research, 1994, ( 72) : 503517.5 Cha B C, et a l. The joint replenishment and delivery scheduling of the one-warehouse, n retailer