不确定因素下路径规划问题研究

发布时间：2018-04-14 00:19

本文选题：旅行商问题 + 车辆路径问题　；参考：《中国科学技术大学》2016年博士论文

【摘要】：随着社会经济和电子商务的快速发展,客户对货物的配送需求迅猛增加,门到门的快递配送服务占据越来越大的配送比例,使得负责快递运输的第三方物流公司面临很大的挑战,即如何在有限的时间内,合理地调度运输车辆,在满足客户需求的情况下,使得总运营成本最小,最后一公里的快递配送也成为亟待解决的问题。本文主要针对包含不确定因素的旅行商问题和车辆路径问题进行研究,具体如下：以电子商务环境为背景,对包含随机客户的旅行商问题进行研究。在电子商务环境下,客户每天上网购物存在一定概率,因此对快递配送服务的需求存在一定概率。如果一个快递公司为客户提供配送服务,其将获得一定收入并支付运输成本,为了使得获取的利润最大化,一些电商平台(比如中国著名电商平台一京东)建立自营物流,为部分客户提供物流配送服务,然后将一些偏远地区客户的配送服务外包给成本较低的第三方物流。在这种情况下,电商平台需要确定为哪些客户提供自营物流,并确定相应配送路径,然后将其余客户的配送服务外包给第三方物流。受启发于以上现实情况,提出新的路径优化问题——考虑利润的概率性旅行商问题(The Probabilistic Profitable Tour Problem, PPTP)。该问题假设所有客户具有相同的需求概率,目标为找出一条经过部分客户、期望利润最大的预优化路径,快递员按照预优化路径的顺序对存在实际需求的客户进行访问。文章构造了该问题的非线性规划模型,并设计了求解该模型的遗传算法。通过对几组较小和中等规模的例子进行求解,验证该算法的有效性。随后在PPTP的基础上,对客户需求概率不相同的情况进行研究,提出一类新的路径问题——同时考虑利润与随机客户的旅行商问题(Travelling Salesman Problems with Profits and Stochastic Customers, TSPPSC)。根据期望利润和期望成本的处理方式不同,TSPPSC可分为三个子问题：包含随机客户的选择性旅行商问题(Selective Travelling Salesman Problem with Stochastic Customers, STSPSC)、包含随机客户的奖励收集旅行商问题(Prize-collecting Travelling Salesman Problem with Stochastic Customers, PCTSPSC)以及同时考虑利润和随机客户的旅行商问题(Profitable Tour Problem with Stochastic Customers, PTPSC)。文章给出了这三个子问题的数学模型,然后设计了模拟退火混合遗传算法来对STSPSC问题进行求解,并通过一系列的实验来验证算法的有效性。实验结果表明本章所提算法能够很好的解决这一类新问题。针对旅行时间不确定的车辆路径问题进行研究。由于门到门的快递配送服务占据越来越大的配送比例,负责快递运输的第三方物流公司面临很大的挑战。与此同时,市区内配送车辆增多,使得城市的交通环境不断恶化。车辆配送过程中可能会遇到交通事故、车辆拥堵以及天气骤变等偶然因素,导致车辆行驶速度事先难以预料。例如：同一条道路,车辆在拥堵时刻的行驶时间可能是普通时刻的数倍,甚至数十倍。此时,物流公司的目标不仅仅为使得车辆的总行驶里程最短,而且希望在满足客户需求的情况下,使得车辆的总行驶时间最短。因此,本文放松车辆行驶速度为恒定的假设,假设车辆在道路上的行驶时间服从4个不同的速度函数,每个函数被选中的概率均为25%。这四种速度函数代表四种可能的道路状况。本章衡量运输车辆路线好坏的指标有四个,分别为车辆行驶总距离、车辆行驶总时间以及每辆车行驶距离和行驶时间的均衡度指标。由于涉及多目标优化,本文根据可行解中四个评价指标的关系,定义它们的支配关系,并设计自适应大规模邻域算法(Adaptive Large Neighborhood Search, ALNS)来寻找问题的Pareto非支配解集。ALNS嵌套在模拟退火算法的框架内,该算法的思想为通过使用移除算子和插入算子来不断的改进初始解,如果新产生的解比当前解要好,则用新产生的解作为下一次迭代的初始解。ALNS分别对单目标CVRP问题和多目标CVRP问题进行求解,通过将单目标CVRP问题的求解结果与标准遗传算法的求解结果和公布的最优解进行比对,验证算法的有效性。然后在四个指标值不同的权重组合下,对单目标CVRP问题的求解结果与多目标CVRP问题的求解结果进行比较分析。
[Abstract]:With the rapid development of social economy and electronic commerce, customer demand for the distribution of goods increased rapidly. The distribution proportion of door to door express delivery service to occupy more and more, the third party logistics company responsible for the express transportation facing great challenges, namely how in the limited time, reasonable scheduling of transport vehicles, to meet the customer demand, so that the minimum total cost of operation, the last mile express delivery has become a serious problem. This paper contains uncertain traveling salesman problem and vehicle routing problem factors were studied as follows: in e-commerce environment as the background, to study the traveling salesman problem contains random customers. Under the environment of e-commerce, online shopping customers every day there are certain probability, so the express delivery service demand there is a certain probability. If a courier company for Provide distribution services to customers, it will get some income and pay the cost of transportation, in order to maximize the profits, some business platform (such as China famous electronic business platform a Jingdong) to establish self logistics, logistics distribution service for some customers, then customers some of the remote areas of the distribution of service outsourcing to the third party logistics cost is low in this case, the electronic business platform to determine the logistics for the customer and to determine the appropriate distribution path, and then the rest of the customer's delivery service outsourcing to the third party logistics. Inspired by the above situation, put forward the new path optimization problem considering the probabilistic traveling salesman problem (The Probabilistic Profitable Tour profit Problem, PPTP). With the same probability of demand assumes that all clients of the problem, the target is to find out a part of the customer, the expected profit maximum The pre optimization path, express access to the actual needs of customers in accordance with the pre optimized path sequence. In this paper, a nonlinear programming model of the problem, and the genetic algorithm is designed. By solving several group of small and medium scale examples verify the effectiveness of the algorithm. Then in the PPTP on the basis of research on customer demand probability is not the same, this paper presents a new class of path problems while considering the traveling salesman problem with stochastic customer profit (Travelling Salesman Problems with Profits and Stochastic Customers, TSPPSC). According to the treatment of expected profits and expected cost is different, TSPPSC can be divided into three sub the traveling salesman problem: including selective random customer problem (Selective Travelling Salesman Problem with Stochastic Customers, STSPSC), including random customers Collect the reward traveling salesman problem (Prize-collecting Travelling Salesman Problem with Stochastic Customers, PCTSPSC) and considering the traveling salesman problem and random profit customers (Profitable Tour Problem with Stochastic Customers, PTPSC). The mathematical model of the three sub problems of this paper, and then design a hybrid genetic simulated annealing algorithm to solve STSPSC problem. And to verify the validity of the algorithm through a series of experiments. The experimental results show that the proposed algorithm can well solve these new problems. To study the vehicle routing problem with travel time uncertainty. Because the distribution proportion of the express delivery service door to door to occupy more and more, is responsible for the express transportation the third party logistics company faces great challenges. At the same time, urban distribution vehicle increased, the city's traffic environment constantly Worse. May encounter traffic accident vehicle distribution process, vehicle congestion and sudden change in the weather and other accidental factors, causing the vehicle speed in advance. For example: There's no telling the same road, the vehicle driving time jam time may be ordinary moments several times, even ten times the number. At this time, the logistics company not only for total travel the shortest mileage of the vehicle, but also hope to meet the customer's requirement, the total vehicle travel time is the shortest. Therefore, the vehicle speed is to relax the assumption of a constant, travel time on the road that vehicles follow 4 different speed function, the probability of each function is selected for the 25%. four speed function represents the four possible road conditions. This chapter measures the routing of transport vehicles quality index four, respectively the total vehicle distance, vehicle travel time and total The equilibrium index of distance and travel time on each car. Due to the multi-objective optimization, based on the relationship between the solutions of four evaluation indexes, the definition of dominance between them, and the design of adaptive large neighborhood algorithm (Adaptive Large Neighborhood Search, ALNS Pareto) to find the problem of non dominated solutions in the framework of nested.ALNS the simulated annealing algorithm, the algorithm is improved by using initial to remove operator and operator to insert the solution, if the new solution is better than the current solution, with a new generation of solution as the initial solution for the next iteration of.ALNS single target CVRP and the multi-objective CVRP problem is solved. By solving the single objective CVRP problem with the standard genetic algorithm and the optimal solution is released for comparison, verify the effectiveness of the algorithm. Then different values in four indicators Under the weight combination, the solution results of the single target CVRP problem and the multi-objective CVRP problem are compared and analyzed.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：U116.2;F252

【相似文献】