车辆派送问题最短行驶路线的建模分析.docxVIP

车辆派送问题最短行驶路线的建模分析摘要车辆派送选取最短的行驶路线是商业公司经常要考虑的问题，一个最优的派送方案可以使公司的费用降到最低，从而使公司的利益最大化。通过建立最优化规划模型来解决最优的车辆行驶路径问题，采用0-1整数规划简化模型，通过Lingo软件进行求解，有效解决了问题2中的具体算例，同时也给出了较普遍的求解这一类车辆行驶路径即问题3当客户i的货物需求量qi为随机参数时的数学模型及处理方法。对于问题1，我们建立的规划模型是在客户的需求量在车辆运送的承载范围之内，我们使用0-1整数规划来解决车辆是否从客户i行驶到客户j这个问题，有效的简化了模型。然后在考虑中心仓库的车辆数约束、车辆的载物量约束、时间约束、客户需求量约束的约束情况下，设立了行驶路径最短的目标函数。并在问题1的具体算例中，利用Lingo软件求得了最优的规划方案：车辆最少数位3辆，行驶路径最短为910公里，路线分别为：0-3-1-2-0，0-8-5-7-0，0-6-4-0。考虑当客户i的货物需求量qi为随机参数的情况下，客户的需求量可能大于车辆的载物量，此时每个客户可能被服务不止一次，我们通过调整约束条件，建立了车辆行驶最短路径的目标函数，使这一类的问题求解有一个更适用的模型。关键词：车辆行径问题；0-1整数规划；目标规划模型；LINGO软件一、问题重述随着社会经济的日益发达和商业活动的日益频繁，合理的货物派送路径成了商业公司密切关注的问题。车辆路径问题（VRP）是指给定一个或多个中心仓库、一个车辆集合和一个客户集合，每个客户有自己不同的货物需求，由车辆集合进行派送，要求在满足一定约束条件的情况下，组织合理的行车路线，达到路径最短、成本最少、或时间最短等目的。一个商品基地，拥有一定数量容量为Q的车辆，负责对N个客户进行货物派送工作，客户i的货物需求量为qi，且，车辆必须在一定的时间范围内到达，早于到达将产生等待损失，迟于到达将处以一定的惩罚，给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具体求解以下算例。1、给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。2、在第一问的基础上，具体求解下面的算例：有8项货物运输任务（编号为1，2，…，8），各项任务的货运量qi（单位：吨）、装货（或卸货）时间si（单位：小时）以及要求每项任务开始执行的时间范围[,]（具体可参看附录中的表一），这些任务由车场0发出的容量为8吨的车辆来完成，车场0与各任务点以及各任务点间的距离（单位：公里）（具体见附录中的表二）。这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短。3、在前两问的基础上，进一步讨论当客户i的货物需求量qi为随机参数时的数学模型及处理方法。二、问题分析对于问题1建立派送费用最小的车辆行驶路径的数学模型，其实就是根据约束条件利用0-1变量建模。首先我们设置0-1变量，一是车辆去不去某个任务点，二是车辆由某个任务点去不去另一个任务点。针对上述变量，我们分别设立约束条件。同时我们为了满足题目所要求的派送费用最小的行驶路径，我们将运输费用与运输距离的乘积作为目标函数，在LINGO软件中，通过设立约束条件，最后将目标函数进行最优化求解。对于问题2，是在第一问的基础上对具体问题的求解，过程参照问题1的过程。对于问题3，是在前两问的基础上解决当客户对货物的需求量qi为随机变量时的情况下车辆的派送费用最小的行驶路径问题。这时，我们除了考虑前两问的因素外，应重点研究客户的需求量有可能大于车辆的容量问题，此时货物可以被拆分，一个客户可能被服务多次。在考虑满足客户的需求量的基础上，我们再考虑使出驶车辆数最少，最后考虑车辆的行驶路径最短。三、模型的假设与符号说明3.1 模型的假设1、假设每辆车需要一定的固定成本，且相等；2、假设车辆在满载及空车时行驶速度相同、运费相同；3、送货期间，车辆之间互不影响；4、模型一与模型二是建立在车辆的载物量大于客户的需求量下；5、模型三是建立在车辆的载物量可能小于客户的需求量的情况下。3.2 符号说明1、Yki=1表示第k辆车子服务第i个客户；2、Yki=0表示第k辆车子不服务第i个客户；3、Xijk=1表示第k辆车子从客户i行驶到客户j ；4、Xijk=0表示第k辆车子不从客户i行驶到客户j；5.C1为相对与运行时间的费用系数；6、Cij表示从点i到点j的运输成本；7、dij表示车辆从客户i行驶到客户j的路程；8、tij表示从客户i到客户j的时间；9、si表示第i种货物装货与卸货的时间；10、qi表示客户i的货物需求量；11、n表示派遣的车辆数量；12、N表示客户数量。四、模型建立与求解4.1 模型一的建立根据我们对问题的分析，在满足客户需求量不大于配送车辆载物量