派送费用最优模型..doc

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