本文選題：城市公共自行車系統(tǒng)　切入點：調(diào)度優(yōu)化算法　出處：《上海交通大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：面對目前日益嚴重的城市道路的擁堵和不斷惡化的氣候環(huán)境,在政府的大力引導(dǎo)扶持和人們健康環(huán)保理念逐漸增強的背景下,自行車這種健康、無污染的交通出行方式又逐漸重新返回人們的視線。然而,由于受到交通流不平衡和通勤出行高峰的影響,城市公共自行車系統(tǒng)(Public Bicycle System,PBS)經(jīng)常出現(xiàn)因站點無車而無法租車和因站點車位滿而無法還車的尷尬現(xiàn)象。這一問題極大地挫傷了人們選擇自行車出行的熱情,阻礙了城市公共自行車系統(tǒng)作用的有效發(fā)揮。本文以當(dāng)前PBS系統(tǒng)中租車還車困難問題為研究對象,在優(yōu)化計算理論和車輛路徑問題(VRP)的基礎(chǔ)上,研究了系統(tǒng)的智能調(diào)度優(yōu)化問題,包括多車調(diào)度任務(wù)的協(xié)調(diào)分配、靜態(tài)調(diào)度路線的構(gòu)建和動態(tài)調(diào)度任務(wù)的在線優(yōu)化等問題,提出了基于聚類劃分的動態(tài)區(qū)域調(diào)度模型、基于遺傳算法的調(diào)度路線構(gòu)建方法和基于迭代反饋雙層模型的動態(tài)調(diào)度方案,在滿足站點調(diào)度請求和保證站點服務(wù)能力的基礎(chǔ)上實現(xiàn)了調(diào)度路線的優(yōu)化,為系統(tǒng)調(diào)度管理提供了決策支持和智能解決方案。首先,為解決PBS系統(tǒng)多車調(diào)度時的調(diào)度車輛的站點分配問題,本文根據(jù)區(qū)域調(diào)度模型提出了基于K-medoids算法的多階段再優(yōu)化動態(tài)聚類的多車調(diào)度任務(wù)分割算法,實現(xiàn)了按照距離、任務(wù)量和站點需求的調(diào)度區(qū)域的動態(tài)劃分和多車輛任務(wù)的協(xié)調(diào)。其次,本文研究了PBS靜態(tài)調(diào)度問題,建立了以最小化調(diào)度費用為目標(biāo)的整數(shù)規(guī)劃模型,提出了基于VRP問題和自適應(yīng)遺傳算法的調(diào)度路線構(gòu)建方法。本文結(jié)合PBS調(diào)度問題的實際需要對遺傳算法進行了改進,定義了染色體逆序數(shù)距離并應(yīng)用最小誤差校正分析技術(shù)實現(xiàn)不可行個體的轉(zhuǎn)換,通過基于雙向關(guān)聯(lián)度的不變位交叉算子、基于種群多樣性和個體適應(yīng)性的自適應(yīng)變異算子、2-opt局部優(yōu)化方法來提高求解精度和加快算法的收斂速度。第三,本文研究了PBS動態(tài)調(diào)度問題,建立了以最大化站點服務(wù)能力和最小化調(diào)度費用為目標(biāo)的數(shù)學(xué)模型,提出了基于需求預(yù)測模型和調(diào)度規(guī)劃模型的迭代反饋動態(tài)調(diào)度求解方案,采用GM(1,1)模型預(yù)測站點調(diào)度需求,采用“需求距離比”和Pareto占優(yōu)排序兩種思路實現(xiàn)調(diào)度規(guī)劃模型,通過禁忌策略防止長時間得不到服務(wù)的“饑餓站點”的產(chǎn)生和延遲偏離當(dāng)前調(diào)度路線的“病態(tài)站點”的服務(wù)時間。此外,基于模塊化和面向?qū)ο蟮脑O(shè)計方法實現(xiàn)了本文的調(diào)度優(yōu)化算法,并用宜興市PBS運營數(shù)據(jù)和TSP/VRP測試實例庫對本文算法進行了仿真分析。最后采用B/S架構(gòu)的Web服務(wù)模式開發(fā)了調(diào)度仿真系統(tǒng),為用戶提供了從瀏覽器調(diào)用本文算法和顯示執(zhí)行結(jié)果的接口。
[Abstract]:In the face of the increasingly serious city road congestion and worsening of the climate and environment, in the government's strong support and guide people to the concept of environmental health gradually under the background of the bicycle health, no pollution of the traffic mode and gradually return to people's attention. However, due to influence of the traffic flow imbalance and commuting peak the city public bicycle system (Public Bicycle System, PBS) often appear due to car rental and car free site by site parking is full to the car of the embarrassing phenomenon. This problem greatly dampened the enthusiasm of people cycling, hinder the effective play the role of city public bicycle system. Based on the car the car is difficult problem in current PBS system as the research object, theoretical calculation and optimization of vehicle routing problem (VRP) on the basis of the study of intelligent scheduling system Optimization problems, including multi vehicle scheduling task allocation, online optimization problems such as construction of static scheduling and dynamic route scheduling tasks, and proposes a dynamic scheduling model based on regional clustering, genetic algorithm scheduling route construction method and dynamic scheduling scheme based on double iterative feedback model, to meet the site scheduling request and guarantee based on site service ability to realize the optimization of scheduling route, provide decision support and intelligent solutions for system scheduling management. Firstly, the problem of distribution system for the site PBS vehicle scheduling of vehicles based on regional scheduling model segmentation algorithm is proposed to multi vehicle scheduling optimization of multi stage dynamic clustering based on the K-medoids algorithm, realized by distance, dynamic coordination and regional task partition scheduling and the site needs and multi task vehicle Secondly, this paper studies the PBS static scheduling problem, integer programming model is established to minimize the scheduling cost as the goal, proposed the construction method for the VRP problem and the adaptive genetic algorithm based on the actual needs. Route scheduling based PBS scheduling problem to improve the genetic algorithm, the definition of reverse distance and chromosome analysis technology to achieve infeasible individual conversion using the minimal error correction, the fixed position of two-way crossover operator based on correlation, adaptive mutation operator of population diversity and individual adaptability based on the solution to improve the precision of 2-opt local optimization method and accelerate the convergence speed. Third, this paper studies the PBS dynamic scheduling problem, establishes the mathematical model with the greatest the site service capacity and minimizing the scheduling cost as the goal, proposed an iterative model and scheduling planning model based on demand forecasting Dynamic feedback scheduling scheme, using GM (1,1) model to predict site scheduling needs, the demand distance ratio and Pareto dominant sort of two ideas to achieve planning scheduling model, the tabu strategy is not a long time to prevent the service "the Hunger Site" and delayed to deviate from the current route scheduling "sick site" the Business Hours. In addition, the modular design method and object-oriented scheduling optimization algorithm based on the use of Yixing city PBS operation data and TSP/VRP test case base on this algorithm are simulated and analyzed. Finally the B/S architecture of the Web service model developed a scheduling simulation system, this algorithm provides from the browser and display the results of the implementation of interface for the user.

【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U495;U491.225

【參考文獻】

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

1 蔡曉妍;戴冠中;楊黎斌;;譜聚類算法綜述[J];計算機科學(xué);2008年07期

2 柳祖鵬;李克平;朱曉宏;;基于蟻群算法的公共自行車站間調(diào)度優(yōu)化[J];交通信息與安全;2012年04期

3 董紅召;史彩霞;陳寧;劉冬旭;;基于關(guān)聯(lián)規(guī)則的公共自行車調(diào)度區(qū)域聚類劃分[J];科技通報;2013年09期

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

1 姚明珠;公共自行車租賃系統(tǒng)建模及評價研究[D];華中科技大學(xué);2012年

，

本文編號：1564463