I车辆调度问题启发式算法研究 摘 要 车辆调度问题启发式算法研究 摘 要 车辆优化调度问题是现代物流系统优化中关键的一环， 也是开展电子商务活动中不可缺少的内容。 对车辆优化调度理论与方法进行系统研究是构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。 本文主要研究了一类车辆优化调度问题：PDPTW 问题 （Pickup and Delivery Problem with Time Windows，带时间窗口的装卸货问题） 及其扩展问题的优化调度算法。 有时间窗口的装卸货问题 （PDPTW）是个运筹学问题， 同时它又是组合优化问题中一个典型的 NP-hard 问题，因此成为运筹学与组合优化领域的研究的难点与热点问题。 在已有研究工作的基础上， 本文分析了该问题及其扩展问题的性质，并提出了一种新的启发式调度方法，并设计开发了辅助车辆调度的软件决策平台。本文的主要研究成果如下: 1分析研究有关 PDPTW 问题的标准算例库，为算法的测试分析奠定了坚实的基础。调试原有的禁忌搜索算法，用标准算例库进行了测试分析，并根据得到的结果，对禁忌搜索算法进行进一步分析和验证。 2提出线性化 1-PDPTW 问题模型的方法，并运用 GLPK 软件包编写程序分析单条路径的优化程度，辅助对算法性能的分析。 3在对禁忌搜索算法测试分析的基础上，以快速减少车辆数目II为目标，提出了一种独特的启发式算法。这是一种基于局域搜索和随机扰动思想的启发式算法。先强制将短路径的客户插入到长路径，使得快速搜索到局部最小点， 再用随机扰动跳到另一个区域重新开始搜索。用此算法对插入算法得到的可行解进行迭代改进，可以迅速并且极大地提高解的质量。 4在上述算法的基础上，进行了改进和扩展研究，使其性能更好、能够处理更复杂的 PDPTW 问题：在插入算法构造初始解的阶段，对于不同特性的算例采用不同的初始解构造方法， 使得构造的初始解更加有效， 更加稳定； 随后提出处理多货物类型及多车库问题的方法，在对快速算法做很小改变的情况下， 使其可以适应多车库问题的求解要求。 5在对 PDPTW 问题有深刻理解的基础上， 本文设计并开发了 车辆调度决策与监控平台 。本软件是用于第三方物流公司的车辆调度与仿真平台，主要解决物流公司根据运输任务进行路径规划、车辆合理分配的问题，同时还可以在配合 GPS、GSM 系统对车辆进行实时监控， 及时对突发事件进行处理。 软件使用中涉及到对地理信息数据库、车辆信息数据库、订单数据库的维护，以及调度任务的决策。在对PDPTW 问题的研究分析中，该软件仿真平台也起到了辅助作用。 关键词: 关键词: 车辆调度，PDPTW 问题，禁忌搜索算法，启发式算法，插入算法，局域搜索 IIIHeuristic Algorithm Research of Vehicle Scheduling Problem ABSTRACT Vehicle optimal scheduling problem is the key part of modern logistics system, and also the indispensable portion of the e-business activities. To study the theory and method of vehicle optimal scheduling problem is the basis of constructing the integrated logistics system, establishing modern scheduling system, developing the intelligent transportation system and developing the e-business. In this paper, a class of vehicle optimal scheduling problem, PDPTW (Pickup and Delivery Problem with Time Windows) and its extended problems are studied. Pickup and Delivery Problem with Time Window (PDPTW) is a typical operations research problem, and is also a typical NP-hard problem in combinational optimization. So it is a tough and popular problem in the field of both operational research and combinational optimization. Based on the work already achieved, the properties of this problem are analyzed, a quick heuristic algorithm is proposed to solve the PDPTW. And a software developed for help solving Vehicle Routing Problem is introduced. The main contributions of this paper are as follows: 1. The benchmark problem of PDPTW has been analyzed, which IVhelps following research work. Debug the original Tabu-Search Method, test on benchmark problem. Based on the result, give the analysis of Tabu-Search Method. 2. Create the method to linearise 1-PDPTW problem. Program for testing and analyzing single route has been developed with GLPK software, which has helped research on the capability of algorithms. 3. A quick heuristic algorithm is proposed to solve the PDPTW. This algorithm is based on the idea of local search and random disturbance. With emphasis on reducing the vehicle number as its main target, this algorithm can get good solutions quickly. Benchmarks for PDPTW have been used to test the algorithm, and the results indicate that this algorithm has its own advantages in computing speed and reducing vehicle number compared with taboo-search method. 4. Based on the quick algorithm, improvement and expansion has been made, in order to improve the capability: in the phases of finding initial solution, using different heuristic insertion methods to solve PDPTW problems which has different characteristic can achieve better result. And then a method to solve multi-depot and multi kinds of goods PDPTW problems has been introduced. 5. Design and Develop the Vehicle Routing Problem Decision Making Platform, which can help third-part logistic company to make scheduling plan. And with help of GPS, GSM system, it can monitor the Vtransport process and help solve emergency. This software has also helped research work on PDPTW algorithm. Key works: Vehicle Scheduling problem, Pickup and delivery problem with time windows (PDPTW), Tabu-search algorithm, heuristic algorithm, Insertion Heuristic, Local Search 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。 除文中已经注明引用的内容外， 本论文不包含任何其它个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：姜政 日期：2006 年 2 月 23 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、 使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。 本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密不保密。 （请在以上方框内打“”） 学位论文作者签名：姜政 指导教师签名：席裕庚 日期：2006 年 2 月 23 日 日期：2006 年 2 月 23 日 上海交通大学硕士学位论文 1第一章 绪论 第一章 绪论 1.1 问题的背景和意义 1.1 问题的背景和意义 物流12是在特定的社会经济大环境中，由运输、存储、包装、配送、装卸、搬运等若干个相互依赖、相互制约的子系统集合而成的具有特定功能的有机整体。 物流配送是物流中一个重要的直接与消费者相连的环节， 是货物从物流结点送达收货人的过程。物流配送过程主要包括3：从生产工厂进货并集结的集货作业； 根据各个用户的不同要求， 在配送中心将所需要的货物挑选出来的配货作业；考虑配送货物的质量和体积， 充分利用车辆的载重和容积的车载货物的配装和配送路线的确定。 诸如 20 世纪 70 年代早期的石油危机这样的经济事件， 以及军事财政的迅速减少，极大地刺激了私有企业、政府机构和学术研究人员投入巨大精力和财力去寻找改进物流、分配和运输的方法。因此配送系统优化成为很多企业和政府机构降低成本、节约能源、