车辆分配问题 ]

《车辆分配问题 ]》由会员分享，可在线阅读，更多相关《车辆分配问题 ]（10页珍藏版）》请在金锄头文库上搜索。

1、南京理工大学 09 数学建模竞赛车辆调度问题题目 A论文题目：有时间窗的多超市多供货点的车辆调度问题论文作者：李少楠 (0704220135) 刘俊豪 (0707390124) 袁 星 (0704220156) （第 110 组）指导老师：许春根 2009-6-1有时间窗的多超市多供货点的车辆调度问题2摘要：本问题是多个供货点对多个超市供货的优化问题，是运筹学当中一个很重要的部分，和实际联系的非常紧密。运输过程中遵循两个基本原则：1.使超市及时得到货物；2.尽量减少供货成本。减少供货成本实际是要解决运输路线的优化问题，而超市及时得到货物相当于超市规定了货物运达的时间窗口，因此各供货中心的发车时

2、间由超市所要求到达的时间而定,本文在解决不能有两辆以上车卸货这一问题时，把一个超市的卸货时间看作一个资源为 2 的变量，当有一辆车卸货时，资源减为 1，当有两辆车卸货时，资源变为 0，也就意味着其他车不能再停车卸货。本文建模的思想是从最简单入手，先仅考虑路径的选择，其实就是各个超市之间的送货顺序，然后加入车辆容量的限制，在送往下个超市之前，车载货物量必须大于超市的需求量，才能运货。然后加入时间约束，各个超市给出货物运达的时间范围，货物必须在这个时间范围内送到，而以上是对单个供货中心而言，最终将所有的供货点连接成网络，由简到繁，层层推进。主要采用了 C-K 节约算法，每增加一个条件限制，相应的算

3、法就进行改进，最终得到最完善的模型。本文还进行了实例分析，计算结果表明了方案的正确性，实际可操作性。最后对模型的优缺点进行了总结，提出了改进思路。关键词：时间窗口 车辆调度 C-K 算法 货物配送有时间窗的多超市多供货点的车辆调度问题30 引 言车辆调度问题(Vehicle Scheduling Problem)首先由 Dantzig 和 Ramser 于 1959 年提出，它主要探讨：组织的行车路线，能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下，有序地通过一系列供应点或需求点，达到诸如路程最短、费用最小，耗费时间尽量少等目的 1 。本文综合应用多种

4、运筹技术求解方法，提出一种寻求多供货点到城市多超市路径的方法，为多供应点、多需求点、带有时间窗口、能接受两辆车同时在同一供货点供货的条件下的车辆调度问题提供了较好的解决方案，并且根据现实中的一个实例给出了具体的求解过程得出有效的对策。1 提出问题并分析建模1.1 问题描述某公司有 n 个超市遍布在城市的四面八方，超市的货物由公司的 m 歌供货中心配给。假设 m 个供货中心存储的货物各不相同，每个供货中心有若干辆供货车给所有的超市供货，每辆车负责若干个超市的供货任务。在一天内，每个超市只接受 m 个供货中心供货各一次，但不能接受两辆以上的供货车同时供货。假设每个超市接受供货车的时间窗口(区间)

5、及每辆车在各超市卸货的大约时间是已知的。a) 为使各超市及时的得到货物补充及减少个供货中心的供货成本，建立模型确定每辆车的供货路线及发车时间；b) 提出求解以上模型的方法；c) 用具体的数据说明模型及方法的有效性；d) 讨论模型的优缺点及改进的思路。设某城市某公司有 M 个供应点（0，1，2，m） ，N 个需求点即超市（0,1,2,n） 。第i 个超市的货运量 gi（i=1，2，n） ，供货点发出车辆的容量为 q（qg i,i=1,2,n） 。车在 i 超市的卸货时间已知为 Ui，第 i 个超市最早、最迟允许车辆到达时间为 ETi、L Ti。超市和供货点看做是运输网络中的节点。同一条线路上点

6、i-1 是点前面的相邻点，车辆到达点 i-1 的时间为 RTi-1，到达点的时间为 RTi。以 Cij表示从 i 点到 j 点的运输费用，它的含义可以是距离、费用、时间等，一般根有时间窗的多超市多供货点的车辆调度问题4据实际情况而定。为了安排路线先考虑一个供货点 M 点的路线，以 0 表示。求出可行的路线后在根据约束条件找出最优的路线。1.2 模型中符号说明xijk : 车辆 k 从 i 点行驶到 j 点;yik : 点 i 的货运任务由车辆 k 完成;Cij: 从 i 点到 j 点的运输费用;gi : 第 i 个超市的货运量;RTi: 到达点的时间;Tij： i 到 j 的时间；ETi :

7、最早允许车辆到达时间;LTi:最迟允许车辆到达时间;Ui: i 超市的卸货时间;Zi: 第条线路的运输费用;Cij: 选择从 i 到 j；S（i，j） ：i 到 j 的节约值；j-： 车辆到达及其后面各点不违反时间窗约束的最大允许时间提前量；j+： 车辆到达及其后面各点不违反时间窗约束的最大允许时间推迟量；： 时间窗内的车辆；1.3 模型建立先对一般情况下的车辆调度问题建模（不考虑运输网络的突发情况） 。设：kijxiky1，车辆 k 从 i 点行驶到 j 点0，其他1，点 i 的货运任务由车辆 k 完成0，其他有时间窗的多超市多供货点的车辆调度问题5则可得车辆优化调度的数学模型如下： L1k

8、kNjM1i Cminijxzs.t.i=1，2，n （2）L1kiyk= -1， （5）RTi=RTi-1+Ui+Ti-1,i i=1，2， N； （6）ETiR TiL Ti （7）X=（x ijk）S （10）=2， （11） 说明：约束（1） ，表示第 k 辆车一趟的供货；约束（2）表示任一超市允许不多于 2 辆同时供货；约束（3）表示车辆 k 仅驶入分配给其运输任务的客户；约束（4）表示车辆 k 仅驶入分配给其运输任务的客户；约束（5）表示进入超市卸货，允许进入的车少 1；约束（6）表示到达 i 点的关系。约束（7）到达时间在时间窗内。约束（8）车辆 i 到 j 的取值。约束（9）车

9、辆在 i 点完成的取值。（1）kqg1ikNii=0，1，2，n （4）ikK1jiyxk j=0，1，2，n （3）ik1i0 或 1 i，j=1 ，2， N；k=1，2，L （8）kij0 或 1 i=1，2， N；k=1 ，2，L （9）iy有时间窗的多超市多供货点的车辆调度问题6约束（10）表示车辆的线路必须是连通的。约束（11）表示允许车辆起始值为 2；2 模型求解2.1 不考虑时间窗的路径选择采用 C-K 节约算法的思想，首先把各个客户单独与车场相连，构成条“”（，）初始化线路，第条线路的运输费用为 Zi=C0i+Ci0 （10）然后把客户和客户连接在一起，形成线路“”（，），计算

10、连接后费用“节约值”：S（i，j）= Ci0+C0j-Cij （11）S（i，j）越大，说明把客户和客户连接在一起时总费用节约值越多，因此应优先连接 S（i，j）值大的点和。基于这一原则，约定把只有一个客户的线路（如“” ）称为初始化线路，把包含两个或两个以上客户的线路（如“”）称为已构成线路，则-节约算法可以描述如下：步骤 1：计算费用节约值 S（i，j ），并排列成二维表格。步骤 2：在表格中选择最大元素 S（i，j ）。步骤 3：考察 S（i，j）对应的点和：若点和都在初始化线路上，则连接点和，形成已构成线路“”，转 步骤 4；若点和中有一个点在已构成线路上，且与车场“” 相连，而另一个

11、点在初始化线路上，则连接点和，得到线路“”或“ ” ，转 步骤 4；若点和分别在两条不同已构成线路上，且均与车场相连，则连接点和，得到线路“”，转 步骤 4。步骤 4：划去表格中的第行和第列，即点不能再作为车辆的发点，点不能再作为车辆的收点。步骤 5：若表格中所有元素 S（i，j ）都被划去，则已通过不断连接点对得到完整的旅行线路方案，算法终止；否则，在未划去的元素中选择最大元素，并转步骤 3。有时间窗的多超市多供货点的车辆调度问题72.2 加入车辆容量以上通过 C-K 算法找到可行路径，现在加入车容量约束条件求解调度问题。如果连接后的车辆装载量大于车辆容量，则不允许连接点和。设线路“ ”的货

12、运量为，线路“” 的货运量为 j，只有 i j时，才允许连接点和，形成线路“” 。 i 和 j 通过累加线路上的客户货运量得到。这样可优化许多路线。2.3 加入时间约束对于时间窗约束需要考虑连接点和后会引起车辆到达点的时间发生变化。设 Fj 表示连接点和后车辆到达点的时间变化量，则有： T （12）显然 时，车辆到达点时间提前； ，车辆到达点时间不变；，车辆到达点时间推迟。设表示同一条线路上及其后面各点，表示车辆到达及其后面各点不违反时间窗约束的最大允许时间提前量，表示车辆到达及其后面各点不违反时间窗约束的最大允许时间推迟量，则有：min （13）nirjSirTEmin （14）nirTLn

13、irj因此，当连接点和时，若有且 ，或者且 ，则连接点和后不会违反时间窗约束。利用这一原理，可以编写时间窗约束检验子程序，插入到算法的步骤 3 中，只有在不违反时间窗约束情况下，才允许连接点和。改进的步骤如下:步骤 1：计算 S（i，j），令S （i ，j）S（i ，j），并把集合内的元素 S（i，j）从大到小排序。步骤：选择集合内的第个元素 S（i，j ），考察点和，是否满足下列条件之一：点和均在初始化线路上；点和一个在已构成线路上，且与车场相连，另一个在初始化线路上；点和位于不同线已构成线路上，且都与车场相连。若满足则转步骤，否则转步骤。有时间窗的多超市多供货点的车辆调度问题8步骤：计算若连接点和后车辆的总装载容量，若，转步骤，否则转步步骤。步骤：计算若连接点和后的 值：若 ，转步骤；若 ，计算 ，若 ，转步骤，否则转步骤；若 ，计算 ，若 ，转步骤，否则转步骤。步骤：连接点和，计算车辆到达各个客户的时间。步骤：在集合中消去这个最大元素 S（i，j ）。若 ，算法终止，否则转步骤。2.4 将所有供货点连接成整个网络前面所求出的是从一个供货点所得到的优化路径，然后用最后一个条件，即不能接受两辆以上的供货车同时供货。令单个接收点的车辆为 =2（允许接收货物的车辆）在