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

有时间限制的物资配送车辆路径问题 摘要： 这是一个带有时间约束的车辆路径安排问题，车辆路径问题是指一定数量的各自有不同货物需求的客户，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，并能在一定约束条件下，使客户的需求得到满足且达到诸如路程最短，成本最小，耗费时间最少等目的。 根据题中所给的条件，我们建立了一个求最短路径的模型，所用到的算法是遗传算法，遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然计划过程有哪些信誉好的足球投注网站最优解的方法。我们暂且考虑车辆都在规定时间内到达客户的情况 ，这种做法虽有不妥之处却在一定程度上简化了该模型。我们所建立的模型针对该问题，在需求量、接货时间段、各种费用消耗已知的情况下，采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制、到达每个客户的车辆和离开每个客户的车辆均为1的限制、货物剩余量、时间段限制，目标函数为可行路径长度的最小化。 根据这些约束条件及所建立模型，我们可以编程解决该问题，在本文假设条件下，可得：最短路径为：910公里，发车数量为：3辆，货车行驶路径分别为：0-8-5-7-0,0-3-1-2-0,0-6-4-0 车辆 编号 所执行的任务路线 到达各点的时间 路线长度 货运量 1 0-8-5-7-0 0-1.6-3.9-7.7-13.9 80+75+90+160=405 3+1.5+2.5=7 2 0-3-1-2-0 0-1.5-3.3-5.6-8.8 75+40+65+60=240 4.5+2+1.5=8 3 0-6-4-0 0-2-6-10.8 100+75+90=265 4+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 物资配送任务及其要求 客户 1 2 3 4 5 6 7 8 （吨） 2 1.5 4.5 3 1.5 4 2.5 3 （小时） 1 2 1 3 2 2.5 3 0.8 [1, 4] [4, 6] [1, 2] [4, 7] [3, 5.5] [2, 5] [5, 8] [1.5, 4] 表2 点对之间的公路里程（千米） 0 1 2 3 4 5 6 7 8 0 0 40 60 75 90 200 100 160 80 1 40 0 65 40 100 50 75 110 100 2 60 65 0 75 100 100 75 75 75 3 75 40 75 0 100 50 90 90 150 4 90 100 100 100 0 100 75 75 100 5 200 50 100 50 100 0 70 90 75 6 100 75 75 90 75 70 0 70 100 7 160 110 75 90 75 90 70 0 100 8 80 100 75 150 100 75 100 100 0 二、问题分析 本题属于比较常见的车辆路径问题(VRP)，不同的是，装货点只有一个。车辆路径问题，即对于多个装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制，即时间窗等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、