【作者】 李阳；

【导师】 范厚明；

【作者基本信息】 大连海事大学 ， 交通运输规划与管理， 2018， 博士

【摘要】 交通与物流是支撑社会经济发展的重要行业,车辆路径问题(Vehicle Routing Problem,VRP)作为组合优化和运筹学领域研究的经典和热点问题,主要研究在满足一定约束条件下合理安排车辆的路径方案和调度计划,使得总体的配送服务成本达到优化,其在物资调运、电子商务以及铁路民航、公交线路等交通和物流领域具有极为广阔的应用背景,而在现实生活中,经常出现某些信息无法提前获知的情况,属于不确定问题,因此对贴近实际生产作业环节中的不确定型车辆路径问题进行研究和优化具有较强的理论和现实意义。本文以模糊需求车辆路径问题(Capacitated Vehicle Routing Problem with Fuzzy Demand,CVRPFD)、随机需求车辆路径问题(Capacitated Vehicle Routing Problem with Stochastic Demand,CVRPSD)、动态需求车辆路径问题(Capacitated Vehicle Routing Problem with Dynamic Requests,CVRPDR)为例,对需求不确定型车辆路径问题展开研究。在对不确定规划理论、VRP研究进展以及启发式算法进行综述的基础上,首先分析了经典的CVRP,设计结合变邻域搜索和生物共栖搜索的混合启发式算法求解,算法采取有序编码方式,通过文献算例对比验证和分析表明了混合算法以及模型的有效性。针对CVRPFD,基于先预优化后重调度的两阶段求解思路,本文首先分析和处理了 CVRPFD的客户点模糊需求变量,通过引入模糊可信性理论,结合预设的决策者风险偏好水平,该模糊变量可以通过模糊机会约束参与后续优化环节。依据所构建的CVRPFD模糊机会规划模型,本文设计了两阶段求解混合变邻域禁忌搜索算法,提出了新客户点重调度策略,该策略能解决以往失败点返回先天不足以及适当返回点选取困难的问题,在出现路径失败时依据重调度策略对全部未完全服务子路径展开整体优化,降低额外配送成本,保证所有客户点能接受服务。针对CVRPSD,本文首先对客户点处随机需求变量进行了分析和处理,构建随机机会约束使其可以参与模型优化,随后依据中心极限定理对该约束进行了确定型等价处理,使后续失败路径的调整得以进行。由于随机需求变量的影响,CVRPSD在求解时也有两阶段优化的特点,预优化阶段首先借助随机机会约束规划模型求得路径方案,在出现路径失败时依据所提出的失败点重调度策略重新调整方案,减少额外配送成本。文章设计了结合变邻域搜索和分散搜索的混合算法对CVRPSD展开两阶段优化求解,通过时间复杂性分析和相应确定型CVRP算例、CVRPSD随机问题算例和文献对比分析表明了所构建随机机会约束规划模型以及混合算法的有效性,算例结果表明新的失败点重调度策略能有效减少整体的配送成本。在对模糊和随机因素影响下UVRP进行研究基础上,本文对CVRPDR展开了相关研究,不同于前两个问题两阶段优化的特征,客户点动态需求的特点使得CVRPDR必须通过周期性的多阶段优化来实现求解,其优化策略对最终方案总成本影响较大。文章首先对其动态性进行了分析,随后提出了基于时间片划分的周期性实时重置策略来解决客户点连续出现的问题,其延迟服务机制能均衡新老客户点的服务需求,合理利用时间因素优化客户点服务顺序,减少车辆配送成本。依据上述策略,文章还设计了子路径动态转变的混合变邻域人工蜂群算法来求解CVRPDR,该算法中车辆子路径可在时间片间动态转变,客户点能实现与虚拟中心的转变,契合动态问题的求解特征。更多还原

【Abstract】 Traffic and logistics are essential industries to support the development of social economy,and the vehicle routing problem as a classical and hot issue in combinatorial optimization and operations research,is mainly to arrange the route and scheduling of vehicles reasonably under certain constraints to optimize the overall distribution service cost.In real life,some unknow information often appear in distribution system,the distribution system with unknow information belong to the uncertain problem.Since it has a great wide application background in the fields of material dispatching,electronic commerce,railway civil aviation,bus line and so on,it is of significant theoretical and practical significance to study and optimize the uncertain vehicle routing problem which closed to the actual production operation link.Based on the review of the corresponding uncertain programming theory,VRP research progress and heuristic algorithm,the paper firstly analyzes the classical CVRP.A hybrid heuristic algorithm combining variable neighborhood search and biological symbiotic search is also designed which adopts the sequential coding method.The comparison and analysis of the literature examples show that the hybrid algorithm and the model are effective to CVRP.Based on the two-stage optimization strategy of pre-optimization and rescheduling,the thesis firstly analyzes and deals with the fuzzy demand variables in CVRPFD.By introducing the fuzzy credibility theory and combining with the preset risk preference level of the decision-maker,the fuzzy variable can participate in the follow-up optimization step by fuzzy chance constraint.According to the constructed fuzzy opportunity programming model of the CVRPFD,a two-stage hybrid variable neighborhood tabu search algorithm is designed.And the paper proposes a new client-point rescheduling strategy which can solve the problem of poor return at previous failure points and difficulty in selecting appropriate return points.All the incomplete service sub paths will be rescheduled according to the rescheduling strategy when the path fails,which can reduce the additional cost of distribution and ensure that all the clients receive the service.For CVRPSD,the paper firstly analyzes the random demand variables at the customer point,and a stochastic chance constraint is set to deal with random variables.According to the central limit theorem for the stochastic chance constraint,the deterministic equivalent processing can obtain for random variables.Due to the influence of stochastic demand variables,CVRPSD has the characteristic of two stages optimization in the process,and the optimization stage first obtains the path scheme with stochastic chance constraint programming model,then adjusts the scheme according to the proposed failure point rescheduling strategy when the path failure occurs.A hybrid algorithm combining variable neighborhood search and scatter search is designed to solve the two-stage optimization of CVRPSD.Through the analysis of time complexity and comparison of corresponding CVRP and CVRPSD instances,it shows that the stochastic chance constraint programming model and hybrid algorithm are effective.The results of instances show that the new failure point rescheduling strategy can effectively reduce the overall distribution cost.Based on the research of UVRP under the influence of fuzzy and stochastic factors,the paper studies the CVRPDR which is different from the two-stage optimization features of the first two problems.The characteristic of dynamic customer demand makes the CVRPDR has to realize the solution through periodic multistage optimization.And the optimization strategy has great influence on the total cost of the final scheme.The paper firstly analyzes the dynamic characteristic of the new customers appear after the optimization is begin,and then puts forward a periodic real-time reset strategy based on time slice partition to matter the need of dynamic customers.And the vehicle delay service mechanism can balance the service demand of new and old customers which will reduce the cost of vehicle delivery.According to the above strategy,the hybrid variable neighborhood artificial colony algorithm is designed to solve the CVRPDR and it allows the sub path of vehicle routing scheme to be changed dynamically between time slices which is more suitable for dynamic problem solving.更多还原