【国家级精品课程】-中南大学-数学建模-lingo-matlab-优化建模-数模培训-全国赛论文-物流车辆调度问题研究.doc

物流车辆调度问题研究摘要物流车辆优化调度是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。通过对配送车辆进行优化调度，企业可以降低运输成本，提高顾客服务水平和经济效益，从而获得更多的利润, 而该类问题的解决在于寻找有效的装配方案和行车路线。本文以基本车辆路径问题(vrp)为基础，通过建立数学模型，寻找车辆调度的最优方案，从而为中心仓库提供明确的车辆调度方案。在中心仓库所收到客户订单的货物需求量qi是已知固定不变的情况下，通过对基本车辆路径问题的分析，分别建立模型和模型，得到在有时间窗问题下，车辆调度的最优方案。模型：带软时间窗的车辆路径优化模型带软时间窗的车辆路径问题由于与车辆数目及时间(装卸货时间和每项任务执行时间)有关，因此我们首先对需要的车辆数目进行一个估计，并使线路安排具有一定的弹性。然后确定在软时间窗条件下的时间函数，同时，在考虑行驶线路的连通性以及一辆车所承担的任务量之和不大于车的容量等约束条件的情况下，建立总派送费用最小的车辆路径优化模型。最后提出一种可以求解这一模型且效果较好的粒子群算法(pso)。模型：带硬时间窗的车辆路径优化模型基于模型的带软时间窗的车辆路径优化模型，我们在对模型简化中将客户对任务执行时间的要求增加，要求车辆必须在一定的时间范围内到达，不能提前也不能拖后，从而建立了带硬时间窗的车辆路径优化模型。在假设车辆数为3的前提下，利用lingo8.0软件求解该模型，得到最优化路径的总运行最短距离min z=910，同时求得车辆的路径分配方案：车1：0-6-4-0；车2：0-3-1-2-0；车3：0-8-5-7-0。模型：带时间窗的随机需求的车辆路径优化模型由于带时间窗的随机需求vrp问题中，客户i的货物需求量qi为随机参数，情况更贴近实际但却使得问题的复杂程度大大增加，为此我们引入了qi的概率分布函数，并考虑了客户需求量小于车辆k剩余运输能力的可能性以及满足车辆在时间窗内到达第i个客户的置信水平，从而在基本的车辆路径问题(vrp)基础上建立了带时间窗的随机需求的车辆路径优化模型。最后，通过分析两种分车辆路径问题，即静态的车辆路径问题(svrp)(模型和模型)和动态的车辆路径问题(dvrp)(模型)，结合车辆路径问题中经常遇到的车辆的装载能力、不同货品之间的装载问题以及客户需求量的随机性等情况，我们向中心仓库提出调整车的容量、缩减或调整车的数量、分道规划等建议。一、问题重述1.1 基本情况一个中心仓库，拥有一定数量容量为q的车辆，负责对n个客户进行货物派送工作，客户i的货物需求量为qi，且车辆必须在一定的时间范围内到达，早到达将产生等待损失，迟达将处以一定的惩罚。1.2 问题提出(1)给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。(2)有8项货物运输任务(编号为1，2，8)，各项任务的货运量 (单位：吨)、装货(或卸货)时间 (单位：小时)以及要求每项任务开始执行的时间范围由表1(附录1.1)给出，这些任务由车场0发出的容量为8吨的车辆来完成，车场0与各任务点以及各任务点间的距离(单位：公里)由表2(附录1.2)给出。这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短。 (3) 进一步请讨论当客户i的货物需求量为随机参数时的数学模型及处理方法。二、问题分析车辆路线问题(vehicle routing problem,简称vrp)考虑从一个或多个中心点出发的车辆将货物发送至一系列顾客并最后回到中心点,问题的解决在于寻找有效的行车路线,使总运行费用最省或者总运行距离最短。为此需要对中心点的车辆建立一个合理的最优线路分配方案，使中心点以最少的成本获得最大的经济效益对于带软时间窗的vrp问题，可以在适当增加等待成本或接受迟到惩罚的前提下减少总成本，在总收益不变的情况下实现中心仓库获利的最大化；硬时间窗vrp问题中，由于只能在给定的时间窗内到达客户处，中心仓库在派送车辆时必须在满足客户时间窗要求的前提下最小化派送总成本；当客户需求为随机需求时，车辆在执行任务时根据自身的剩余运输能力以及下一客户的随机需求以一定的概率决定是不是继续服务下一个客户，以概率形式最优化车辆得总运行路径。三、模型假设(1)单物流中心，非满载，单车型，多目标配送问题；(2)中心仓库拥有的车辆足够多；(3)不考虑货物的品名和包装，以及配送车辆的类型，货物可以混装；(4)装货(或卸货)的较简单及约束较少；(5)不考虑在货物运输和配送过程中，由于交通事故、天气变化等偶发因素等可能在造成的车辆旅行时间的变化；(6)每辆车最多被使用一次，每位客户有且只有一辆车服务，并且没有重复路线。四、符号说明q ：是车辆平均容量大小；qi : 第i个客户的货物需求量；n : 是客户的数量；si : 表示客户i处装货(或卸货)所需时间；tij : 表示从客户j处到客户i处所需时间；ai : 每项任务开始执行的时间；bi : 每项任务结束的时间；v ：是每辆车的平均行驶速度。以上为符号说明的不完全归纳，其余符号说明见具体模型五、模型的建立与求解车辆路线问题是考虑在车队为一些有需求的顾客运送货物时如何安排行驶路线,从而使服务效率达到最高,在原有车辆路线问题的基础上,着重考虑车辆路线问题中客户的随机性及客户接受服务的时间窗约束,建立车辆路径优化模型,并用粒子群算法进行求解, 寻找有效的行车路线,使总运行费用最省及总运行距离最短。下图为车辆路径问题的基本示意图。图5.1 车辆路径问题示意图5.1 带软时间窗的车辆路径优化模型由题意可知，该题是在基本车辆路径(vrp)问题上加了客户要求访问的时间窗口的带时间窗的车辆路径问题(vehicle routing problem with time windows, vrptw )，为此我们建立了带软时间窗的车辆路径模型。为求解这一模型，我们采用粒子群算法(pso , particle swarm optimization)，它是最近出现的一种模拟鸟群飞行的仿生算法,与一般的启发式算法相比有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将将pso 应用于车辆路径问题求解中, 取得了很好的效果。5.1.1 模型的准备(1)车辆数的确定一般来说，当问题的约束越多，组织线路就越难，一辆车所完成的满足所有约束的任务就越少，这时，一辆车实际所能容纳的任务量要小，而所用的车辆数可能要多。为了安排路线，须预先对需要的车辆数进行一个估计。为了使线路安排具有一定的弹性，可按下式确定车辆数: (1)式中， 表示不大于括号内数字的最大整数；0a6-4-0；表5.2 车二的行驶路线：012345678012345678000100000001000000100000000010000000000000000000000000000000000000000000000000000可知：车二的行驶路径为：0-3-1-2-0；表5.3车三的行驶路线：012345678012345678000000001000000000000000000000000000000000000000000010000000000100000000000001000 可知：车三的行驶路径为：0-8-5-7-0。5.3 带时间窗的随机需求vrp优化模型在实际问题中，顾客的需求往往是随机的，即客户i的货物需求量 为随机参数，因此我们在模型i的基础上将静态的vrp(svrp)模型转化为动态的vrp(dvrp)模型。5.3.1 模型的准备假设顾客的需求和车辆到达顾客的时间是随机的，并且服从的分布为；某一车辆k服务s(sn)个客户后，其总运载量为；车辆k的剩余运载能力为；下一客户需求量小于车辆k剩余运输能力的可能性为。在客户的需求为随机需求时，当车辆k的剩余运输能力越大，下一个客户的需求量越小，该车能够服务下个客户的机会就越大，我们希望车辆k服务下一客户时，下一个客户的需求量不超过车辆k剩余运输能力的可能性满足置信水平。对于给定的值，在车辆路径的安排过程中，当p时，该车辆k继续完成下个客户的运输任务，若p，则该车返回车场，新派车完成剩余运输任务。重复上述过程，直到客户排列中所有客户都安排完毕，这样可产生一个可行的车辆安排。但在实际的配送过程中，由于需求量的随机性，当车辆k按计划的可行路径达到某个客户时，可能会由于车辆剩余运输能力不能满足该客户需求而导致任务失败，车辆只能返回车场卸货后空驶至该失败点继续完成剩余运输任务，从而产生额外的行驶距离。同时给每个顾客分配一个满足车辆在时间窗内到达的置信水平,于是有下面的约束条件：，5.3.2 模型的建立由模型的准备我们建立带时间窗的随机需求vrp数学模型，该模型同样满足模型中的约束条件。模型iii目标函数 (24)约束条件 (25) (26) (27) (28) (29) (30) (31) 模型中， ：从任务点i到任务点j的距离； ：车辆k的额外行驶距离；z：总计划路径距离与额外行驶距离之和；式(24)：表示总计划路径距离与额外行驶距离之和最小的目标；式(25)：表示车辆k承担的任务量之和不大于车辆的容量的概率满足置信水平；式(26)：表示任务i只能由一辆车完成；式(27)：表示由车场0发出m辆车；式(28)：表示保证每个客户点处有且仅有一辆车访问一次；式(29)：保证了进入和离开一给定客户点的车辆数相同；式(30)：保证车辆行驶线路的连通性，即车辆到达了一个客户节点，从该点离开；式(31)：车辆到达客户的时间在客户时间窗内的概率满足置信水平。 六、给中心送货仓库的建议在模型二中，通过对几个约束条件分析得到货运量与车自身容量成为约束中心仓库最优化送货的重要条件。适当调整会对中心仓库得到更优化效益。所以，向中心送货仓库提出如下建议：(1)对车的载货性能主要为车的容量进行调整。因为线路不同，客户需求量不同，对于不同方向不同客户量采取不同型号(容量)车运送。对于一方向大量需求和另一方向少量需求采用同种容量车运货只会造成资源不足或资源浪费。所以，应在仓库多配备不同运货性能的车以便采取合理的派送分配；(2)缩减或调整车的数量。因为对于一些派送方案，最大车辆运送并不能带来最优效益，可以适当缩减主运车数，调整备用车辆以备突发性需求运输；(3)采取分道规划。可以对以往客户需求进行数据统计，得到分布函数，知道不同方向大致需求以便能对将来需求做预测，对于需求较大需求稳定的客户点进行路径规划，配备专门车辆随时准备运输以减少临时调度损失；(4)规范送货制度。一套完整的制度体系对于人员调度是十分必要的，人员规范化必然也能带来送货规范化。七、模型评价 物流车辆调度过程中，虽然受到很多影响因素的共同影响，但是主要的影响因素为时间、车场、车型、任务和目标为代表的影响因素对一般物流车辆调度问题的影响，每一种因素对车辆调度的影响特点具有自己的特点。就本文所建立的3个模型，模型的带时间窗的随机需求vrp模型相对于模型的静态的带软时间窗的车辆路径模型，更实际具有实际意义，因为对svrp而言，相关信息不会发生变化，但在实际过程中，由于交通流量、天气变化、交通事故等因素的影响，行驶速度总在不断变化，从而导致各个路段上的运行时间也发生相应变化。因此在考虑客户货物需求量 在服从一定的概率分布后的随机需求vrp模型具有一定的推广价值。八、参考文献：1 刘霞，车辆路径问题的研究，/grid2008/detail.aspx?filename=2009033564.nh&dbname=cdfd2009，2007.6.1；2 石勇，物流车辆调度问题研究，/grid2008/detail.aspx?filename=2008036225.nh&dbname=cmfd2008， 2007.11；3 李宁、邹彤、孙德宝，带时间窗车辆路径问题的粒子群算法，/grid2008/detail.aspx?filename=xtll200404020&dbname=cjfq2004，2004.4；4 吴斌，车辆路径问题的粒子群算法研究与应用，/kns55/detail/detail.aspx?dbcode=cdfd&dbname=cdfd2008&filename=2008041106.nh&filetitle=，2007.11；5 徐玖平、胡知能、王委 编著，运筹学(第二版)，科学出版社，2004.5；6 盛丽俊，带有时间窗的车辆路径问题的优化研究，/periodical_shhyxyxb200704014.aspx， 2003.3；7 高明霞、杨涛、张春民，带时间窗的随机需求车辆路线问题的模型研究，/periodical_lztdxyxb200403002.aspx，2004.6；8 徐芳，基于随机需求的道路货物调运方法研究，/jiaotongyunshu/467152.html， 2008.4；9 曹二保、赖明勇、张汉江，模糊需求车辆路径问题研究，/qk/93285x/2007011/26319383.html，2007.11；10 陈宝文、宋申民、陈兴林，随机需求车辆路径问题及其启发式算法, /qk/95033x/200701/24041974.html，2007.1。九、附录：附录1.1表1 任务的特征及其要求任务12345678(吨)21.54.531.542.53(小时)121322.530.81,44,61,24,73,5.52,55,81.5,4附录1.2表2 点对之间的距离 01234567801 23456780406075902001001608040065401005075110100606507510010075757575407501005090901509010010010001007575100200501005010007090751007575907570070100160110759075907001008010075150100751001000附录1.1 lingo求解程序model: !定义原始级和派生级；sets: points/0,1,2,3,4,5,6,7,8/:f； point_aim/1,2,3,4,5,6,7,8/:timea,timeb,q,s； roads(points,points):dist,x1,time_between； cars/1.3/； reach/1 2 3 4 5 6 6 7 8/:time_reach； road_car(roads,cars):x； task_car(points,cars):y； task_aim(point_aim,cars):y1； endsets!数据输入；data: dist=0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110 100 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 80 100 75 150 100 75 100 100 0； m=3； timea=1 4 1 4 3 2 5 1.5； timeb=4 6 2 7 5.5 2.5 8 4； q=2 1.5 4.5 3 1.5 4 2.5 3； s=1 2 1 3 2 2.5 3 0.8； capacity=8； time_between=0 0.8 1.2 1.5 1.8 4 2 3.2 1.6 0.8 0 1.3 0.8 2 1 1.5 2.2 2 1.2 1.3 0 1.5 2 2 1.5 1.5 1.5 1.5 0.8 1.5 0 2 1 1.8 1.8 3 1.8 2 2 2 0 2 1.5 1.5 2 4 1 2 1 2 0 1.4 1.8 1.5 2 1.5 1.5 1.8 1.5 1.4 0 1.4 2 3.2 2.2 1.5 1.8 1.5 1.8 1.4 0 2 1.6 2 1.5 3 2 1.5 2 2 0；enddata!目标函数；min=sum(roads(i,j): dist(i,j)* sum(cars(k): x(i,j,k)；!定义x为0，1变量；for(road_car:bin(x)；!定义y为0，1变量；for(task_car:bin(y)；for(task_aim:bin(y1)；!约束条件；!约束一：表示k承担的任务量之和不大于车的容量；sum(point_aim(i): q(i)*sum(cars(k)|k#eq#1: y1(i,k)=capacity；sum(point_aim(i): q(i)*sum(cars(k)|k#eq#2: y1(i,k)=capacity；sum(point_aim(i): q(i)*sum(cars(k)|k#eq#3: y1(i,k)sum(point_aim(i):timea(i)；for(reach(j):time_reach(j)sum(point_aim(j):timeb(j)；end附录1.2 lingo求解结果global optimal solution found at iteration: 21 objective value: 910.0000 variable value reduced cost m 3.000000 0.000000 capacity 8.000000 0.000000 f( 0) 0.000000 0.000000 f( 1) 0.000000 0.000000 f( 2) 0.000000 0.000000 f( 3) 0.000000 0.000000 f( 4) 0.000000 0.000000 f( 5) 0.000000 0.000000 f( 6) 0.000000 0.000000 f( 7) 0.000000 0.000000 f( 8) 0.000000 0.000000 timea( 1) 1.000000 0.000000 timea( 2) 4.000000 0.000000 timea( 3) 1.000000 0.000000 timea( 4) 4.000000 0.000000 timea( 5) 3.000000 0.000000 timea( 6) 2.000000 0.000000 timea( 7) 5.000000 0.000000 timea( 8) 1.500000 0.000000 timeb( 1) 4.000000 0.000000 timeb( 2) 6.000000 0.000000 timeb( 3) 2.000000 0.000000 timeb( 4) 7.000000 0.000000 timeb( 5) 5.500000 0.000000 timeb( 6) 2.500000 0.000000 timeb( 7) 8.000000 0.000000 timeb( 8) 4.000000 0.000000 q( 1) 2.000000 0.000000 q( 2) 1.500000 0.000000 q( 3) 4.500000 0.000000 q( 4) 3.000000 0.000000 q( 5) 1.500000 0.000000 q( 6) 4.000000 0.000000 q( 7) 2.500000 0.000000 q( 8) 3.000000 0.000000 s( 1) 1.000000 0.000000 s( 2) 2.000000 0.000000 s( 3) 1.000000 0.000000 s( 4