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

物流车辆调度问题研究摘要物流车辆优化调度是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。通过对配送车辆进行优化调度，企业可以降低运输成本，提高顾客服务水平和经济效益，从而获得更多的利润, 而该类问题的解决在于寻找有效的装配方案和行车路线。本文以基本车辆路径问题(VRP)为基础，通过建立数学模型，寻找车辆调度的最优方案，从而为中心仓库提供明确的车辆调度方案。在中心仓库所收到客户订单的货物需求量是已知固定不变的情况下，通过对基本车辆路径问题的分析，分别建立模型和模型，得到在有时间窗问题下，车辆调度的最优方案。模型：带软时间窗的车辆路径优化模型带软时间窗的车辆路径问题由于与车辆数目及时间(装卸货时间和每项任务执行时间)有关，因此我们首先对需要的车辆数目进行一个估计，并使线路安排具有一定的弹性。然后确定在软时间窗条件下的时间函数，同时，在考虑行驶线路的连通性以及一辆车所承担的任务量之和不大于车的容量等约束条件的情况下，建立总派送费用最小的车辆路径优化模型。最后提出一种可以求解这一模型且效果较好的粒子群算法(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的货物需求量为随机参数，情况更贴近实际但却使得问题的复杂程度大大增加，为此我们引入了的概率分布函数，并考虑了客户需求量小于车辆k剩余运输能力的可能性以及满足车辆在时间窗内到达第i个客户的置信水平，从而在基本的车辆路径问题(VRP)基础上建立了带时间窗的随机需求的车辆路径优化模型。最后，通过分析两种分车辆路径问题，即静态的车辆路径问题(SVRP)(模型和模型)和动态的车辆路径问题(DVRP)(模型)，结合车辆路径问题中经常遇到的车辆的装载能力、不同货品之间的装载问题以及客户需求量的随机性等情况，我们向中心仓库提出调整车的容量、缩减或调整车的数量、分道规划等建议。一、问题重述1.1 基本情况一个中心仓库，拥有一定数量容量为Q的车辆，负责对N个客户进行货物派送工作，客户i的货物需求量为，且车辆必须在一定的时间范围内到达，早到达将产生等待损失，迟达将处以一定的惩罚。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 ：是车辆平均容量大小；: 第i个客户的货物需求量；N : 是客户的数量； 表示客户i处装货(或卸货)所需时间；: 表示从客户j处到客户i处所需时间； : 每项任务开始执行的时间； : 每项任务结束的时间；v ：是每辆车的平均行驶速度。以上为符号说明的不完全归纳，其余符号说明见具体模型五、模型的建立与求解车辆路线问题是考虑在车队为一些有需求的顾客运送货物时如何安排行驶路线,从而使服务效率达到最高,在原有车辆路线问题的基础上,着重考虑车辆路线问题中客户的随机性及客户接受服务的时间窗约束,建立车辆路径优化模型,并用粒子群算法进行求解, 寻找有效的行车路线,使总运行费用最省及总运行距离最短。下图为车辆路径问题的基本示意图。图5.1 车辆路径问题示意图5.1 带软时间窗的车辆路径优化模型由题意可知，该题是在基本车辆路径(VRP)问题上加了客户要求访问的时间窗口的带时间窗的车辆路径问题(Vehicle Routing Problem With Time Windows, VRPTW )，为此我们建立了带软时间窗的车辆路径模型。为求解这一模型，我们采用粒子群算法(PSO , Particle Swarm Optimization)，它是最近出现的一种模拟鸟群飞行的仿生算法,与一般的启发式算法相比有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将将PSO 应用于车辆路径问题求解中, 取得了很好的效果。5.1.1 模型的准备(1)车辆数的确定一般来说，当问题的约束越多，组织线路就越难，一辆车所完成的满足所有约束的任务就越少，这时，一辆车实际所能容纳的任务量要小，而所用的车辆数可能要多。为了安排路线，须预先对需要的车辆数进行一个估计。为了使线路安排具有一定的弹性，可按下式确定车辆数: (1)式中， 表示不大于括号内数字的最大整数；0<a<1是对装货(或卸货)的复杂性程度及约束多少的估计，一般来讲，装(卸)货越复杂，约束越多，a应越小，表示一辆车所能容纳的货物量越少。实际中a的大小可以调整。(2)时间的确定车辆到达客户i的时间为: (2)5.1.2 模型的建立先定义以下变量: (3) (4)则得到相对于硬时间窗的VRP问题的数学模型如下: 模型：目标函数： (5)约束条件： (6) (7) (8) (9) (10) (11) 模型中， :从任务点到任务点的运输成本，目标不同，它的含义也有所不同，可以是距离、费用、时间等，一般根据实际情况确定。 Z：总派送费用；d：等待损失的单位机会成本；e：表示车辆在要求时间后到达所处以的单位惩罚值。即若车辆在之前到客户i指定点，则产生成本。若车辆在之后到达客户i指定点，则处以惩罚。式(5 ):表示费用极小的目标； 式(6 ):表示车辆k承担的任务量之和不大于车辆的容量； 式(7 ):表示任务i只能由一辆车完成； 式(8 ):表示由车场0发出m辆车； 式(9 ):表示保证每个客户点处有且仅有一辆车访问一次； 式(10):保证了进入和离开一给定客户点的车辆数相同； 式(11): 保证车辆行驶线路的连通性，即车辆到达了一个客户节点，也必须从该点离开。5.1.3 模型的求解基于以上模型，我们运用粒子群算法(PSO)来求解(1)算法的理论粒子群算法是对鸟觅食过程的迁徙和集群行为的模仿。PSO通过粒子间的相互作用搜索复杂空间中的最优区域，是一类基于迭代的随机全局优化算法。在PSO 系统中, 每个备选解被称为一个“粒子”(Particle) , 多个粒子共存、合作寻优(近似鸟群寻找食物) , 每个粒子根据它自身的“经验”和相邻粒子群的最佳“经验”在问题空间中向更好的位置“飞行”, 搜索最优解。在粒子群算法中，每个粒子表示n维空间的一个解，则第i个粒子的状态为，每个粒子的速度向量为。每个粒子经历过的最优状态记做，群体经历过的最优状态用表示，在t+l时刻状态更新方程如下所示: (12) (13)其中，是惯性权重，是加速度常数。从社会心理学的角度解释，表示粒子对自身当前信息的依赖情况，表示粒子对自身经验的依赖情况，表示粒子对社群信息的依赖情况。rand()表示0到1间的随机数。粒子群算法分为两个版本，全局版和局部版。上述是全局版定义，局部版与它的区别在于几表示局部领域内的最优解而非全局最优。(2)算法的实现前面所述PSO 算法为连续空间算法, 而VRP问题为整数规划问题, 因此在算法实现过程中要作相应修改。具体实现步骤如下:Step1:构造一个2L维的空间对应有L个客户任务的VRP问题, 每个客户任务对应两维: 完成该任务车辆的编号k， 该任务在k车行驶路径中的次序r。为表达和计算方便, 将每个粒子对应的2L维向量X分成两各L维向量:(表示各任务对应的车辆编号)和(表示各任务在对应的车辆路径中的执行次序)Step2:初始化粒子群粒子群划分成若干个两两相互重叠的相邻子群；每个粒子位置向量的每一维随机取1K(车辆数) 之间的整数, 的每一维随机取1L(客户任务数)之间的实数；每个速度向量的每一维随机取-(K-1)(K-1)(车辆数)之间的整数,的每一维随机取-(L- 1)(L- 1)之间的实数；用评价函数Eval评价所有粒子；将初始评价值作为个体历史最优解并寻找各子群内的最优解 和总群体内最优解。Step3 重复执行以下步骤, 直到满足终止条件或达到最大迭代次数每一个粒子, 按式(12)计算 按照式(12) 计算, 其中向上取整； 当V、X 超过其范围时按边界取值。 用评价函数Eval评价所有粒子； 若某个粒子的当前评价值优于其历史最优评价值, 则记当前评价值为该历史最优评价值, 同时将当前位置向量记为该粒子历史最优位置； 寻找当前各相邻子群内最优和总群体内最优解, 若优于历史最优解则更新。对于子群内有多个体同为最优值的情况, 则随机取其中一个为子群内当前最优解Z其中, 评价函数Eval完成以下任务:1) 根据公式(5)计算该粒子所代表路径方案的行驶成本Z， 在计算中客户任务的执行次序要根据对应值的大小顺序, 由小到大执行；2) 将按执行顺序进行重新整数序规范。根据前面的定义和计算过程，粒子群算法求解车辆路径问题的具体流程图如下图5.2所示初始化粒子群计算粒子的适应度选择个体历史最有位置选择群体最优位置根据定义的速度、状态计算方法根据定义进行状态更新满足终止条件否是结束，输出结果图5.2 粒子群算法流程图(3)算法的分析从粒子群算法的流程可以看出，算法的计算时间主要花费在迭代过程中，对于种群规模为P，迭代次数为N，问题规模为L的问题，其每次迭代，都要经过解码，适应度计算，个体、群体最优状态选择和速度计算，状态更新几个步骤。其中解码阶段使用最邻近法对解调整，时间复杂度是，适应度的计算时间复杂度是，群体最优位置选择的时间复杂度是，个体最优位置的时间复杂度是，在进行速度计算时，粒子的状态更新的时间复杂度是，而每次更新需要计算两次速度即个体部分的速度和最优部分的速度，状态更新的总的时间复杂度是。这样整个算法的时间复杂度为: 从上式可以看出，算法的计算量与问题规模的平方成正比，种群规模和迭代次数都影响计算时间。算法计算量和一般的启发式算法在一个量级，是一个好算法。5.2 带硬时间窗的车辆路径优化模型 对于8项货物运输任务(编号为1，2，8)，各项任务的货运量(单位：吨)、装货(或卸货)时间为的具体情况，类似于模型I，我们建立了带硬时间窗的车辆路径模型。5.2.1 模型的准备 (1)车辆数的确定由模型I为了使线路安排具有一定的弹性，可按下式确定车辆数: 再由假设(4)我们在此取,并由上式可得K=3(2)时间的确定由模型I(2)式，车辆到达客户i的时间为: 且 我们通过Excel软件对题中车场0与各任务点以及各任务点间的距离进行处理，得出车场0与各任务点以及各任务点间所需的运行时间。5.2.2 模型的建立 变量定义与模型I相同，由此可得模型II 目标函数 (14)约束条件 (15) (16) (17) (18) (19) (20) (21) 模型中， :从任务点到任务点的距离；Z：总运输距离；式(14):表示费用总运输距离最小的目标； 式(16):表示车辆k承担的任务量之和不大于车辆的容量； 式(17):表示任务i只能由一辆车完成； 式(18):表示由车场0发出m辆车； 式(19):表示保证每个客户点处有且仅有一辆车访问一次； 式(20):保证了进入和离开一给定客户点的车辆数相同； 式(21): 保证车辆行驶线路的连通性，即车辆到达了一个客户节点，也必须从该点离开； 5.2.3 模型的简化在具体求解第二问时，我们在此假设客户要求货物必须在规定的时间窗内送到，不能提前也不能拖后，即将模型I的软时间窗问题转化成硬时间窗问题，这样将问题简化。因此添加必要的约束条件 (22) (23)式(22)(23)：车辆到达客户必须满足的时间要求。5.2.4 模型的求解我们首先用matlab7.0软件对表2的原始数据数据进行处理，得到距离矩阵和速度矩阵。然后利用lingo8.0软件求解VRPHTW模型(附录1.1)，求得min Z=910，即最优化路径的总距离，同时求得车辆的路径分配方案。明确的分配方案如下表所示：(附录1.2)表5.1 车一的行驶路线：(注：1为可走，0为不可走，下同)012345678012345678000000100000000000000000000000000000100000000000000000000010000000000000000000000可知车1的行驶路径为：0->6->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(s<N)个客户后，其总运载量为；车辆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 刘霞，车辆路径问题的研究，2 石勇，物流车辆调度问题研究， 2007.11；3 李宁、邹彤、孙德宝，带时间窗车辆路径问题的粒子群算法，4 吴斌，车辆路径问题的粒子群算法研究与应用，5 徐玖平、胡知能、王委 编著，运筹学(第二版)，科学出版社，2004.5；6 盛丽俊，带有时间窗的车辆路径问题的优化研究， 2003.3；7 高明霞、杨涛、张春民，带时间窗的随机需求车辆路线问题的模型研究，8 徐芳，基于随机需求的道路货物调运方法研究， 2008.4；9 曹二保、赖明勇、张汉江，模糊需求车辆路径问题研究，10 陈宝文、宋申民、陈兴林，随机需求车辆路径问题及其启发式算法, 九、附录：附录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)<=capacity；!约束二：表示任务i只能由一辆车完成；for(point_aim(i): sum(cars(k): y1(i,k)=1)；!约束三：表示由中心仓库0出发m量车；sum(task_car(i,k)|i#eq#1:y(i,k)=m；!约束四：表示每个客户点只有一辆车访问；for(points(j)|j#ne#1: sum(points(i): sum(cars(k):x(i,j,k)=1)；!约束五：保证进入和离开一客户点的车辆数相同；for(points(p): sum(points(i)|i#ne#p: sum(cars(k): x(i,p,k)=1； sum(points(j)|j#ne#p: sum(cars(k): x(p,j,k)=1； )；!约束六：时间约束；for(reach(i):time_reach(i)>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