本文選題：旅行商問題 + 車輛路徑問題��； 參考：《中國科學(xué)技術(shù)大學(xué)》2016年博士論文

【摘要】：隨著社會經(jīng)濟和電子商務(wù)的快速發(fā)展,客戶對貨物的配送需求迅猛增加,門到門的快遞配送服務(wù)占據(jù)越來越大的配送比例,使得負責(zé)快遞運輸?shù)牡谌轿锪鞴久媾R很大的挑戰(zhàn),即如何在有限的時間內(nèi),合理地調(diào)度運輸車輛,在滿足客戶需求的情況下,使得總運營成本最小,最后一公里的快遞配送也成為亟待解決的問題。本文主要針對包含不確定因素的旅行商問題和車輛路徑問題進行研究,具體如下：以電子商務(wù)環(huán)境為背景,對包含隨機客戶的旅行商問題進行研究。在電子商務(wù)環(huán)境下,客戶每天上網(wǎng)購物存在一定概率,因此對快遞配送服務(wù)的需求存在一定概率。如果一個快遞公司為客戶提供配送服務(wù),其將獲得一定收入并支付運輸成本,為了使得獲取的利潤最大化,一些電商平臺(比如中國著名電商平臺一京東)建立自營物流,為部分客戶提供物流配送服務(wù),然后將一些偏遠地區(qū)客戶的配送服務(wù)外包給成本較低的第三方物流。在這種情況下,電商平臺需要確定為哪些客戶提供自營物流,并確定相應(yīng)配送路徑,然后將其余客戶的配送服務(wù)外包給第三方物流。受啟發(fā)于以上現(xiàn)實情況,提出新的路徑優(yōu)化問題——考慮利潤的概率性旅行商問題(The Probabilistic Profitable Tour Problem, PPTP)。該問題假設(shè)所有客戶具有相同的需求概率,目標(biāo)為找出一條經(jīng)過部分客戶、期望利潤最大的預(yù)優(yōu)化路徑,快遞員按照預(yù)優(yōu)化路徑的順序?qū)Υ嬖趯嶋H需求的客戶進行訪問。文章構(gòu)造了該問題的非線性規(guī)劃模型,并設(shè)計了求解該模型的遺傳算法。通過對幾組較小和中等規(guī)模的例子進行求解,驗證該算法的有效性。隨后在PPTP的基礎(chǔ)上,對客戶需求概率不相同的情況進行研究,提出一類新的路徑問題——同時考慮利潤與隨機客戶的旅行商問題(Travelling Salesman Problems with Profits and Stochastic Customers, TSPPSC)。根據(jù)期望利潤和期望成本的處理方式不同,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)。文章給出了這三個子問題的數(shù)學(xué)模型,然后設(shè)計了模擬退火混合遺傳算法來對STSPSC問題進行求解,并通過一系列的實驗來驗證算法的有效性。實驗結(jié)果表明本章所提算法能夠很好的解決這一類新問題。針對旅行時間不確定的車輛路徑問題進行研究。由于門到門的快遞配送服務(wù)占據(jù)越來越大的配送比例,負責(zé)快遞運輸?shù)牡谌轿锪鞴久媾R很大的挑戰(zhàn)。與此同時,市區(qū)內(nèi)配送車輛增多,使得城市的交通環(huán)境不斷惡化。車輛配送過程中可能會遇到交通事故、車輛擁堵以及天氣驟變等偶然因素,導(dǎo)致車輛行駛速度事先難以預(yù)料。例如：同一條道路,車輛在擁堵時刻的行駛時間可能是普通時刻的數(shù)倍,甚至數(shù)十倍。此時,物流公司的目標(biāo)不僅僅為使得車輛的總行駛里程最短,而且希望在滿足客戶需求的情況下,使得車輛的總行駛時間最短。因此,本文放松車輛行駛速度為恒定的假設(shè),假設(shè)車輛在道路上的行駛時間服從4個不同的速度函數(shù),每個函數(shù)被選中的概率均為25%。這四種速度函數(shù)代表四種可能的道路狀況。本章衡量運輸車輛路線好壞的指標(biāo)有四個,分別為車輛行駛總距離、車輛行駛總時間以及每輛車行駛距離和行駛時間的均衡度指標(biāo)。由于涉及多目標(biāo)優(yōu)化,本文根據(jù)可行解中四個評價指標(biāo)的關(guān)系,定義它們的支配關(guān)系,并設(shè)計自適應(yīng)大規(guī)模鄰域算法(Adaptive Large Neighborhood Search, ALNS)來尋找問題的Pareto非支配解集。ALNS嵌套在模擬退火算法的框架內(nèi),該算法的思想為通過使用移除算子和插入算子來不斷的改進初始解,如果新產(chǎn)生的解比當(dāng)前解要好,則用新產(chǎn)生的解作為下一次迭代的初始解。ALNS分別對單目標(biāo)CVRP問題和多目標(biāo)CVRP問題進行求解,通過將單目標(biāo)CVRP問題的求解結(jié)果與標(biāo)準(zhǔn)遺傳算法的求解結(jié)果和公布的最優(yōu)解進行比對,驗證算法的有效性。然后在四個指標(biāo)值不同的權(quán)重組合下,對單目標(biāo)CVRP問題的求解結(jié)果與多目標(biāo)CVRP問題的求解結(jié)果進行比較分析。
[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.

【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：U116.2;F252

【相似文獻】

相關(guān)期刊論文 前10條

1 劉冠佳;劉水強;;一類多出發(fā)點多旅行商問題規(guī)劃算法[J];山東理工大學(xué)學(xué)報(自然科學(xué)版);2011年02期

2 呂善國;曹義親;陳紅麗;;求解旅行商問題的一種新方法[J];華東交通大學(xué)學(xué)報;2012年05期

3 徐心和;旅行商問題的一種新解法[J];東北工學(xué)院學(xué)報;1990年01期

4 徐心和,唐加福;用路徑代數(shù)求解旅行商問題的新結(jié)果[J];東北工學(xué)院學(xué)報;1993年04期

5 黨建武,陳軼星;時間多項式進化算法在旅行商問題中的研究(英文)[J];蘭州鐵道學(xué)院學(xué)報;2001年01期

6 國圓媛;許延鑫;吳江;;浙江旅行商問題研究[J];中國新技術(shù)新產(chǎn)品;2009年22期

7 李成兵;彭其淵;郭倩倩;程嘉;;改進蟻群算法在旅行商問題中的應(yīng)用[J];鐵道運輸與經(jīng)濟;2009年02期

8 陳培軍;王欣潔;;旅行商問題的近似求解算法[J];太原科技大學(xué)學(xué)報;2010年03期

9 高春濤;;用蟻群算法求解旅行商問題[J];哈爾濱商業(yè)大學(xué)學(xué)報(自然科學(xué)版);2009年04期

10 李炳宇,蕭蘊詩;基于模式求解旅行商問題的蟻群算法[J];同濟大學(xué)學(xué)報(自然科學(xué)版);2003年11期

相關(guān)會議論文 前10條

1 馮純伯;;旅行商問題的一種解法[A];1991年控制理論及其應(yīng)用年會論文集（下）[C];1991年

2 張雷;鄭維敏;;廣義旅行商問題、放映員問題和一類調(diào)度模型[A];1996年中國控制會議論文集[C];1996年

3 胡巧華;吳懷宇;陳喬禮;陳媛;;一種求解旅行商問題的啟發(fā)交叉算子的研究[A];第25屆中國控制會議論文集（中冊）[C];2006年

4 張輝;王錫淮;肖健梅;;基于改進蟻群算法的旅行商問題[A];2007中國控制與決策學(xué)術(shù)年會論文集[C];2007年

5 李大衛(wèi);王夢光;;熱軋調(diào)度與多旅行商問題[A];1996年中國控制會議論文集[C];1996年

6 劉春波;潘豐;楊丹;;基于改進的蟻群算法在中國旅行商問題中的求解[A];2007中國控制與決策學(xué)術(shù)年會論文集[C];2007年

7 馮純伯;蔣珉;;應(yīng)用模擬電場法解旅行商問題[A];1993年控制理論及其應(yīng)用年會論文集[C];1993年

8 李麗;程玉榮;牛奔;;離散人工蜂群算法求解旅行商問題[A];第十三屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2011年

9 孫啟瑞;李俊;丁健;戴先中;;新型訪問域部分重疊的多旅行商問題的GA求解[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第四分冊）[C];2013年

10 韓愛麗;朱大銘;;旅行商問題的一種新DNA編碼方案[A];2006年全國理論計算機科學(xué)學(xué)術(shù)年會論文集[C];2006年

相關(guān)博士學(xué)位論文 前3條

1 張夢穎;不確定因素下路徑規(guī)劃問題研究[D];中國科學(xué)技術(shù)大學(xué);2016年

2 譚陽;求解廣義旅行商問題的若干進化算法研究[D];華南理工大學(xué);2013年

3 王剛;兩類圈問題的算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 劉欣欣;旅行商問題的基因片段插入算法研究[D];閩南師范大學(xué);2015年

2 陳玲;基于PSO-GA混合算法的時間優(yōu)化的旅行商問題的研究[D];合肥工業(yè)大學(xué);2015年

3 徐東鎮(zhèn);蟻群算法及其在廣義旅行商問題求解中的應(yīng)用[D];合肥工業(yè)大學(xué);2007年

4 黃厚生;求解旅行商問題的新方法研究[D];天津大學(xué);2005年

5 王玲麗;隨機存儲下的有容量限制的廣義旅行商問題[D];上海交通大學(xué);2012年

6 高峰;求解多目標(biāo)旅行商問題的進化算法研究[D];華東師范大學(xué);2013年

7 覃錦華;求解旅行商問題的進化算法[D];西安電子科技大學(xué);2008年

8 李天龍;基于自組織優(yōu)化算法的多旅行商問題的求解與應(yīng)用[D];浙江大學(xué);2010年

9 南小康;樹算法求解旅行商問題[D];蘭州大學(xué);2008年

10 劉仁洪;一種改進的蟻群算法求解旅行商問題[D];山東大學(xué);2008年

，

本文編號：1746878