车辆分配问题 ].docVIP

南京理工大学09数学建模竞赛 车辆调度问题 题目A 论文题目：有时间窗的多超市多供货点的车辆调度问题 论文作者：李少楠 (0704220135) 刘俊豪 (0707390124) 袁 星 (0704220156) （第110组） 指导老师：许春根 2009-6-1  摘要：本问题是多个供货点对多个超市供货的优化问题，是运筹学当中一个很重要的部分，和实际联系的非常紧密。运输过程中遵循两个基本原则：1.使超市及时得到货物；2.尽量减少供货成本。减少供货成本实际是要解决运输路线的优化问题，而超市及时得到货物相当于超市规定了货物运达的时间窗口，因此各供货中心的发车时间由超市所要求到达的时间而定,本文在解决不能有两辆以上车卸货这一问题时，把一个超市的卸货时间看作一个资源为2的变量，当有一辆车卸货时，资源减为1，当有两辆车卸货时，资源变为0，也就意味着其他车不能再停车卸货。本文建模的思想是从最简单入手，先仅考虑路径的选择，其实就是各个超市之间的送货顺序，然后加入车辆容量的限制，在送往下个超市之前，车载货物量必须大于超市的需求量，才能运货。然后加入时间约束，各个超市给出货物运达的时间范围，货物必须在这个时间范围内送到，而以上是对单个供货中心而言，最终将所有的供货点连接成网络，由简到繁，层层推进。主要采用了C-K节约算法，每增加一个条件限制，相应的算法就进行改进，最终得到最完善的模型。本文还进行了实例分析，计算结果表明了方案的正确性，实际可操作性。最后对模型的优缺点进行了总结，提出了改进思路。 关键词：时间窗口 车辆调度 C-K算法 货物配送 0 引 言 车辆调度问题(Vehicle Scheduling Problem)首先由Dantzig和Ramser于1959年提出，它主要探讨：组织的行车路线，能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下，有序地通过一系列供应点或需求点，达到诸如路程最短、费用最小，耗费时间尽量少等目的[1] 。 本文综合应用多种运筹技术求解方法，提出一种寻求多供货点到城市多超市路径的方法，为多供应点、多需求点、带有时间窗口、能接受两辆车同时在同一供货点供货的条件下的车辆调度问题提供了较好的解决方案，并且根据现实中的一个实例给出了具体的求解过程得出有效的对策。 1提出问题并分析建模 1.1问题描述 某公司有n个超市遍布在城市的四面八方，超市的货物由公司的m歌供货中心配给。假设m个供货中心存储的货物各不相同，每个供货中心有若干辆供货车给所有的超市供货，每辆车负责若干个超市的供货任务。在一天内，每个超市只接受m个供货中心供货各一次，但不能接受两辆以上的供货车同时供货。假设每个超市接受供货车的时间窗口(区间)及每辆车在各超市卸货的大约时间是已知的。 为使各超市及时的得到货物补充及减少个供货中心的供货成本，建立模型确定每辆车的供货路线及发车时间； 提出求解以上模型的方法； 用具体的数据说明模型及方法的有效性； 讨论模型的优缺点及改进的思路。 设某城市某公司有M个供应点（0，1，2，…m），N个需求点即超市（0,1,2,…n）。第i个超市的货运量gi（i=1，2，…n），供货点发出车辆的容量为q（qgi,i=1,2,…n）。车在i超市的卸货时间已知为Ui，第i个超市最早、最迟允许车辆到达时间为ETi、LTi。超市和供货点看做是运输网络中的节点。同一条线路上点是点ｉ前面的相邻点，车辆到达点的时间为，到达点ｉ的时间为到达点ｉ的时间 LTi: 最迟允许车辆到达时间; Ui: i超市的卸货时间; Zi: 第ｉ条线路的运输费用（）Δj-： 车辆到达ｊ及其后面各点不违反时间窗约束的最大允许时间提前量Δj+： 车辆到达ｊ及其后面各点不违反时间窗约束的最大允许时间推迟量?： 时间窗内的车辆； 1.3 模型建立 先对一般情况下的车辆调度问题建模（不考虑运输网络的突发情况）。设： 则可得车辆优化调度的数学模型如下： s.t. i=1，2，…n （2） ?= ?-1， （5） ??RTi=RTi-1+Ui+Ti-1,i i=1，2，…， N； （6） ETi≤RTi≤LTi （7） X=（xijk）∈S