有时间限制的物资配送车辆路径问题汇总.doc

有时间限制的物资配送车辆路径问题摘要： 这是一个带有时间约束的车辆路径安排问题，车辆路径问题是指一定数量的各自有不同货物需求的客户，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，并能在一定约束条件下，使客户的需求得到满足且达到诸如路程最短，成本最小，耗费时间最少等目的根据题中所给的条件，我们建立了一个求最短路径的模型，所用到的算法是遗传算法，遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然计划过程搜索最优解的方法我们暂且考虑车辆都在规定时间内到达客户的情况 ，这种做法虽有不妥之处却在一定程度上简化了该模型我们所建立的模型针对该问题，在需求量、接货时间段、各种费用消耗已知的情况下，采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制、到达每个客户的车辆和离开每个客户的车辆均为1的限制、货物剩余量、时间段限制，目标函数为可行路径长度的最小化根据这些约束条件及所建立模型，我们可以编程解决该问题，在本文假设条件下，可得：最短路径为：910公里，发车数量为：3辆，货车行驶路径分别为：0-8-5-7-0,0-3-1-2-0,0-6-4-0车辆编号所执行的任务路线到达各点的时间路线长度货运量10-8-5-7-00-1.6-3.9-7.7-13.980+75+90+160=4053+1.5+2.5=720-3-1-2-00-1.5-3.3-5.6-8.875+40+65+60=2404.5+2+1.5=830-6-4-00-2-6-10.8100+75+90=2654+3=7但是，由于受到我们假设的约束，这样得出的结果未必为最优解，然后我们可用典型的单源最短路径算法即Dijkstra(迪杰斯特拉）算法进行优化，这种算法用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩散，直到扩散到终点为止优化后可得最短路为公里885，三条路径分别为分别为：0-8-5-7-2-0,0-3-1-2-0,0-6-4-0关键词：遗传算法，迪杰特斯拉算法，时间限制，车辆路径一、问题重述物流中心O有容量为Q的车辆若干辆，负责对需求量分别为的个客户进行货物派送工作，客户i的货物需求量为，且，车辆必须在一定的时间范围内到达，否则会有一定的损失，按照要求求解一下两个问题：1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法2. 具体求解以下算例，载重量为 8 吨、平均速度为 50千米/小时 的送货车辆从物流中心（0）出发，为编号是 1，2，…，8 的8个客户配送物资某日，第个客户所需物资的重量为吨（），在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围 由表1给出物流中心与各客户以及各客户间的公路里程（单位：千米）由表2给出问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的具体行驶路径）才能使总运行里程最短 表1 物资配送任务及其要求客户12345678（吨）21.54.531.542.53（小时）121322.530.8[1, 4][4, 6][1, 2][4, 7][3, 5.5][2, 5][5, 8][1.5, 4] 表2 点对之间的公路里程（千米） 0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000 二、问题分析 本题属于比较常见的车辆路径问题(VRP)，不同的是，装货点只有一个。

车辆路径问题，即对于多个装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制，即时间窗等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)要在一定的约束条件下，使得派送总费用最小（派送总费用包括运输成本，车辆在客户要求到达时间之前到达产生的等待损失，车辆在客户要求到达时间之后到达所受惩罚等），相应的，总路程也最短现在就要根据这些约束条件，从而确定最佳派送方案 题中已给定客户i的货物需求量,每个客户的接货时间范围[，]，卸货时间，和物流中心与各客户之间及客户与客户之间的路程，货车最大载重量Q，货车行驶速度v等,因此，我们便要根据题意，选取若干辆车进行送货，然后考虑每辆车负责哪些客户的送货任务我们可以在适当合理的假设下，通过编程，给出满足题中限制条件(各客户时间范围，货车最大载重量，剩余物资等）的很多参考方案，并在不重复的基础上选出使得总路程最小的路径，从而建立最优化模型确定最佳车辆派送方案 三、模型假设 1、车辆不会出现折线行走，即车辆在经过某个客户点时一定卸货。

2、物流中心有足够的资源以及足够的车辆以供配送 3、每辆车送货行驶时不会有突发状况影响车辆的送货计划以及车辆速度 4、每个客户的物资只能由一辆车辆配送四、符号定义与说明物流中心车辆的最大送货量运送车辆的总数第i个客户最早到时间为，第i个客户的最晚到时间第i个客户的所需货物数量i到j的路程车辆从i到j的行驶时间车辆在i处的卸货（等待）时间编号为k的车辆从i走到j所有车辆行驶的总路程i的货物由编号为k的车辆完成车辆的平均行驶速度五、模型建立与求解1、 模型思路给出所有路径（穷举法或图的遍历）——限制条件下求解可行路径（遗传算法）——在求出的路径中选择最短路径（优化）——考虑车辆返回物流中心时可走折线路线，用迪杰特斯拉算法求解最短路径（最优化）2、模型建立（1） 建立二维数组，对从物流中心出发的所有客户进行全排列 或 ‚客户与物流中心均看成点，互相连接，标记其之间距离，使其成为图，图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次本题中，我们采用方法来进行编程2）根据题意，模型所求目标函数为 限制条件为： （车辆k的运输总重不超过车辆的最大载重） （车辆的到达时间在所规定的内） m i=0 = （每个客户的货物只能由一辆车来配送） 1 i=1,2......N = （保证每个到达i点的车辆离开i点） =（3）遗传算法取可行路径 1．编码采用自然数编码，即序数编码。

货物运输路线可以编成长度为N+m的染色体，其中，表示第项任务0表示车场，m表示完成任务所需的车辆数2.出生初始群体初始群体随机产生，即产生项货物运输任务点的全排列，，如果，且，将s至N的数向后移动一位，将0插入第s位接着，继续上述操作，直到m个0全部插入为止这样就构成了一条初始染色体用这种方法构造一个群体的染色体如：031285764，该编码插零之后变成03120857064它代表着需要三辆车运输货物其中，第1辆车行走路线为03120，即从仓库出发到依次到商店再回到仓库第2辆车行走路线为08570，第3辆车行走路线为0640 3.适应度函数适应度函数取，其中为染色体的适应度，b为常数，为初始种群中最好的染色体的运输成本，为染色体对应的运输成本 4.遗传算子选取最佳保留的轮盘赌复制法进行染色体的复制变异算子采用反转变异交叉算子用最大保留交叉，其操作过程为：a) 若染色体交叉点处的两个基因都为0，则直接进行顺序交叉运算；b) 若染色体交叉点处的基因不全为0，则将交叉点左移（右移），直到左右两个交叉处的基因都为0，再进行顺序交叉运算 5.算法的实现步骤a) 初始化：设置进化代数计数器t=0,设置最大进化代数T，随机生成M个个体作为初始群体P(0).b) 个体评价：计算群体P（t)中各个个体的适应度。

c) 选择运算：将选择算子作为群体选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体在遗传到下一代选择操作是建立在群体中个体的适应度评估基础上的d) 交叉运算：将交叉算子作用与群体，所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作遗传算法中起核心作用的就是交叉算子e)变异运算：将变异算子作用于群体即是对群体中的个体串的某些基因座上的基因值作变动群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算4）优化在可行路径中利用计算机程序进行简单的大小比较，取最小值5）再优化 考虑到车辆返回物流中心时可以经过其他的点回到物流中心，利用迪杰特斯拉算法对优化的结果进行再优化 迪杰特斯拉算法（Dijkstra）算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止Dijkstra算法能得出最短路径的最优解其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知初始时，S中仅含有源。

设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度Dijkstra算法每次从V-S中取出具有最短特殊路，长度的顶点u，将u添加到S中，同时对数组dist作必要的修改一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度3.具体模型求解(问题2）题中所给定的条件为8个客户点，车辆载重Q为8吨，平均行驶速度为50公里每小时，其时间限制和所需货物量由表1表2给出 （1）全排列，共有8！次排列方，数量过多，具体在此不列举 （2）遗传算法选取可行路径，并将可行路径设为。