带时间窗的车辆路径问题及其算法研究

第一章绪论

1.1背景与研究意义

1.2主要研究内容与结构安排。

第二章带时间窗车辆路径问题研究现状

2.1车辆路径问题概述

2.2带时间窗车辆路径问题的一般描述与数学模型2.3带时间窗车辆路径问题的分类及其常用求解算法2.4国内带时间窗车辆路径问题研究综述

2.5带时间窗车辆路径问题研究的发展动态

2.6带时间窗车辆路径问题的测试算例

第三章求解VRPTW的插入检测法研究

3.1问题的提出，

3.2插入检测法的概述

3.3前推值插入检测法

3.4时差插入检测法.

3.5测试与比较分析

3.6小结

第四章求解VRPTW的插入启发式算法研究4.1问题的提出

4.2求解VRPTW插入启发式算法的研究意义与研究现状

4.3经典插入启发式算法

4.4时差插入启发式算法

4.5算法测试

4.6小结

第五章带时间窗取送货问题研究

5.1带时间窗取送货问题概述及其研究现状

5.2带时间窗取送货问题的数学模型

5.3求解PDPTW的基本遗传算法

5.4求解PDPTW的非代际遗传算法

5.5测试及比较分析

5.6小结

第六章带工作时间与时间窗的开放式车辆路径问题及其克隆

选择算法研究

6.1引言

6.2问题描述与数学模型

6.3人工免疫克隆选择算法相关理论

6.4求解VRP的基本克隆选择算法

6.5求解OVRPTWWT的克隆选择算法

6.6算例测试

6.7小结

第七章结论与展望

7.1结论

7.2展望

参考文献

第一章绪论

1.1背景与研究意义

物流是指物品从供应地向接收地的实体流动活动。现代物流运用全新的管理理念，通过对物流全过程多要素的计划、实施和控制，将运输、贮存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合，从而为用户提供高效率、多功能、一体化的综合性服务。物流业作为国民经济发展的动脉和基础产业，具有十分重要的地位。在国际上，物流业的发展水平已成为衡量一个国家社会经济发展水平和综合国力的重要指标之一。

随着我国市场经济的快速发展，科学技术的进步以及消费者需求的日益多元化和个性化，物流业作为“第三利润源泉”日益受到企业的关注。20世纪80年代以来，我国政府大力推动物流产业的发展，我国物流业作为一个独立的产业部门迅速崛起，但由于目前我国物流业还处于初步发展阶段，物流运作中的技术运用和管理水平仍处于较低水平，物流规划、仓储管理、合理化运输及物流信息技术等方面的发展还与世界先进水平有较大差距,其中最突出的问题就是物流成本高。因此，近年来国务院和地方各级政府纷纷制定了各种有利于物流产业发展的政策与规划，大力发展现代物流业已被纳入国家发展战略。国务院通过了《物流业调整和振兴规划》，确定了发展多式联运和转运设施、发展物流园区、发展城市配送、发展大宗商品和农村物流、推动制造业和物流业联动发展、推动物流标准和技术推广、发展物流公共信息平台、加强物流科技攻关及发展应急物流等九大重点工程。规划的制订与实施，标志着物流业的振兴发展已上升为国家战略，为了更进一步落实规划精神,国务院又召开专题常务会议，决定从物流产业税收、土地政策，降低过路过桥收费、推进物流技术创新与应用、加大物流业投入和促进农产品物流业发展等方面着手，进一步促进物流业健康发展。

车辆路径问题(VRP)，也称车辆调度问题(VSP)是运输组织优化中的核心问题之一，它通过对车辆的运输路线进行优化，在满足客户需求的前提下，尽量以最低的运输成本与费用将货物送达目的地。车辆路径问题自1959年由Dantzig 和 Ramser首次提出以来，因其对应实践中的大量应用，吸引了大量学者对其理论和应用进行研究，取得了丰富的研究成果。1983年，L.Bodin等学者对VRP的研究进展实行综述时，列举了699篇相关的参考文献;1995年出版的《运筹学与管理科学手册》专门在第八卷讨论车辆路径问题;2002年，Paolo等学者在其著作中，对VRP的一些新的研究进展和发展趋势进行了全面分析。相比与国际，国内VRP的研究起步较晚，但最近几年研究发展较快，1994年，郭辉煌教授等出版了国内该领域的第一部专著《车辆优化调度》，随后在2001年李军教授等出版了《物流配送车辆优化调度理论与方法》，对车辆路径问题的模型与优化方法实行了详细介绍;2006年与2009年，郎茂祥、张潜两位学者分别在其著作中对车辆路径问题最新研究进展进行综述。VRP 已成为近几十年来运筹学领域研究最活跃、成果最精彩的方向之一。

在实践中，该问题的应用不仅仅局限在物流配送领域，在航空、远洋航运、通信、电力、工业管理和计算机应用等领域也有一定的应用，其研究成果已用于轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、垃圾收集线路安排和生产系统中的计划与控制等多种组合优化问题。因此，对车辆路径问题进行广泛和深入的研究，即可以促进运筹学学科的发展，又可将其研究成果应用于现代物流配送与交通运输管理领域，提高运作效率，节约运输成本，具有较高的理论与实践研究价值。

本书主要对带时间窗的车辆路径问题及其算法问题进行探究，首先对时间窗和车辆路径问题以及有关求解车辆路径问题的通用启发式的相关知识进行了简单的介绍，其次深入介绍了关于开放式车辆的路径问题，探讨了关于开放式车辆路径问题的数学模型与研究现状。本书主要采用了文献调查法，通过查阅大量的相关资料来对车辆路径与时间窗问题进行深入的分析与思考，进一步对带软时间窗约束的开放式车辆路径问题进行了介绍，并提出相关模式以及当前的应用前景，围绕农产品物流集货运输路径问题和碳排放约束的车辆路径问题进行了分析研究，本书旨在为带时间窗的车辆路径问题的研究提供一定的实践依据，本书可供带时间窗的车辆路径问题的研究者借鉴与参考。