时间窗约束下的非满载车辆优化调度算法研究

              作者：许传达　高永攀　刘军杰　涂黎明
　　摘要：在车辆优化调度问题上，文章将配送车辆根据任务的性质分成满载和非满载两类问题。针对时间窗约束下的非满载车辆优化调度问题，同时考虑特定的时间窗和车辆容量、行驶距离等约束条件，运用数学规划理论对其进行了研究。并在分析其数学模型的基础上，给出了实例分析，对提高物流配送效率和降低成本具有重要意义。
　　关键词：时间窗；算法；车辆优化调度
　　 　Abstract: On the problem of optimization of vehicle dispatching optimizing, this thesis studying on the distribution freight vehicle, analyses two problems named as full loaded vehicle scheduling problem and non-full loaded vehicle scheduling problem which are classed by the property of the task. For resolving the OVD problem under the time windows and vehicle capacity constraints, as the same time, taking special restrictions such as time window, the capability of vehicle and the run distance into account, the theory of mathematical programming is used. By analyzing the mathematical model of the OVD, its practical example is given, and it is very important to improve the efficiency of logistics distribution and reduce cost.
　　
　　Key words: time windows; algorithm; optimization of vehicle dispatching
　　
　　0引言
　　
　　在汽车运输部（分）队担负的繁重的运输保障任务中，大量存在的时间窗约束下的非满载车辆调度问题，由于没有合理的优化算法支撑，往往得不到较好的解决，致使运输部（分）队保障效率低下、资源浪费现象严重，极大地限制了汽车运输部（分）队保障能力的发挥。因此，研究时间窗约束下非满载车辆优化调度算法，就显得愈发的重要和迫切。
　　
　　1非满载OVD问题的数学模型构建
　　
　　1.1非满载OVD问题的数学模型
　　将输送中心S编号为0，任务编号为1,2,…,L，任务及保障点均以点ii=0,1,…,L来表示，定义变量如下：
　　于是，得到本OVD问题的调度线路为：0→8→5→7→0；0→3→1→2→0；0→6→4→0。
　　
　　3结束语
　　
　　本文提出了时间窗约束下非满载OVD的算法，较好地解决了汽车运输部（分）队车辆调度优化问题。在算法设计过程中，对OVD问题模型结合车辆与货物装载属性进行了全面地讨论，具有较高的实际应用价值。
　　
　　：
　　[1] 吕永波，胡天军，雷黎. 系统工程[M]. 北京：北方大学出版社，2003.
　　[2] 钱颂迪. 运筹学[M]. 北京：清华大学出版社，1999.
　　[3] 吴清一. 物流系统工程[M]. 北京：物资出版社，2004.
　　[4]Ngoin B.K.A, Tay M.L, Chua E.S. Applying Spatial Representation Techniques to the container Packing Problems[J]. International Journal of Production Research, 1994(32):111-123.