带时间窗和二维装载约束车辆路由问题的多目标进化算法研究

《带时间窗和二维装载约束车辆路由问题的多目标进化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、COntents5．1．4RuntimeComparison．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．365．2Resultson2IjVRPTWBenchmark⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。38Chapter6ConclusionandFutureWork．．．．⋯．．．⋯．．．．．．．．．．．．．．．．．⋯．．．⋯．⋯．．．40Referenee．．⋯．⋯．．．⋯．．．

2、⋯．．．⋯．⋯．⋯．．．⋯．．．．⋯．．．⋯．．．⋯．．．．⋯．．．⋯．．．⋯．．．．⋯．．．⋯．．．．．41Acknowledge．．．．⋯．．．⋯．．．．⋯．．．．⋯．．．⋯．⋯⋯．．．⋯⋯．⋯⋯⋯．⋯．．．．⋯．．．．．．．．．⋯．．．⋯．．．．45Publication．．⋯．．．．．⋯⋯⋯．．．⋯．．．⋯．．．⋯．．．．⋯．．⋯⋯．．．．．．．．．⋯．．⋯．．．．．⋯．．．．⋯．．．．．．．．．．．46第一章绪论随着中国经济的迅猛发展，各行各业对物流和运输行业的要求也越来越高。近年来，

3、电子商务的兴盛也促使物流和运输行业进入了一个崭新的发展阶段。物流和运输行业的快速发展为保证国民经济协调、平稳、较快发展发挥了基础和支撑保障作用。而另一方面，中国经济在蓬勃发展的同时，也给自然环境带来了严重污染。最近，全国大范围内“雾霾”现象的出现使人们越来越意识到环境污染的严重性。已有学者认为经济发展不能走“先污染后治理”的道路，应该在经济发展的同时还要考虑减少对环境的污染。为顺应新阶段提出的新要求，物流和运输行业也在积极引入新的技术，在保证服务质量的前提下，优化配置现有的资源，提高资源利用率和

4、降低物流配送的运输成本。而在这其中，一个很重要的问题是：如何分配车辆来服务不同的客户，以何种顺序，何时运送，才能使得车辆按照客户的要求，按时为客户完成服务，并且使得所用的车辆数或者行驶总距离最少。这一问题被学者们建模为车辆路由问题(vehicleroutingproblem)。车辆路由问题需要对车辆进行调度和对车辆路线进行规划，其车辆调度和路线规划方案直接影响着物流配送的速度、成本和效益。目前，国内很多车辆调度和路线规划方案都是凭经验依靠人工完成，这往往需要耗费大量的人力并且难以保证质量。对车辆

5、路由问题的研究，使我们可以通过计算机的自动计算来得到更为高效合理的车辆调度和路线规划方案。1．2研究意义车辆路由问题是运筹学和组合优化领域的研究热点，在物流和运输行业中具有重要的实际应用价值。在我国，经济建设、电子商务等的需求导致物流业和运输业快速发展，物流业和运输业现在尚处于其生命周期的发展时期。全社会的物流和运输成本随着社会发展和社会需求而节节攀升。由于我国这几年社会工业的经济总量巨大，资源利用率的微小提升都能节约大量资源。于是，针对具体的实际物流问题，如何设计高效算法安排合适的车辆路线，从

6、而减小资源的消耗，就1第一章绪论成为当今物流业一个很重要的问题。更好的算法，意味着更少的资源消耗，更低的成本，更好的服务，更高的利润，从而提高企业的盈利能力，获得更多的经济和社会效益。伴随国内经济快速发展而来的是环境的污染。近几年的“雾霾”现象更逐渐让人们意识到低碳经济的重要性。“雾霾”现象的一个重要来源是汽车尾气的过多排放，因此，如果能有高效算法安排经济建设中的车辆调度问题，提高装载利用率，从而降低汽车尾气排放量，将会有益于缓解空气污染等环境问题。至今为止，针对车辆路由问题及其变体问题，国内外

7、学者已经进行了大量研究，发表了各种解决这些问题的方法。本文通过对实际应用中的问题进行建模分析，提出一个更具有实际应用价值的车辆路由变体问题，即多目标的带时间窗和二维装载约束的车辆路由问题(MultiobjectiveVehicleRoutingProblemwithTimeWindowsandTwoDimensionalLoadingConstraint，MO一2LVRPTW)。MO一2LVRPTW是两个经典的车辆路由问题的更一般情况，即带时间窗的车辆路由问题(VehicleRoutingPro

8、blemwithTimeWindows，VRPTW)和带二维装载约束的车辆路由问题(VehicleRoutingProblemwithTwoDimensionalLoadingConstraint，2LVRP)，也是更贴合实际应用需求的问题。本文希望通过提出M0—2LVRPTW这个问题和对这个问题的求解，给国内外研究者们提供一个新思路，并希望能吸引更多学者们关注这个更具实际应用价值的问题。1．3研究内容车辆路由问题最早由Dantzig和Ramser于50多年前提出n1，经典的车辆路由问题(Veh