基于貪心算法的共享單車的優(yōu)化調(diào)度模型

盧泗化 李倩文

摘要：在經(jīng)濟(jì)、科技發(fā)展都如此迅速的信息時(shí)代，共享經(jīng)濟(jì)逐漸發(fā)展壯大，共享單車成為新的四大發(fā)明之一，它改變了人們短途出行方式，隨之而來的共享單車分配成為業(yè)界的關(guān)注焦點(diǎn)。本文主要考慮城市內(nèi)某些單車投放點(diǎn)供求關(guān)系不平衡需要進(jìn)行調(diào)度服務(wù)，使各單車投放點(diǎn)的數(shù)量保持動(dòng)態(tài)平衡，根據(jù)已知數(shù)據(jù)利用貪心算法在一定的約束范圍內(nèi)，制定出共享單車的調(diào)度方案，同時(shí)滿足人們對(duì)共享單車的需求及調(diào)度成本最小，希望有助于共享單車的優(yōu)化調(diào)度。

關(guān)鍵詞：調(diào)度模型 供求不平衡 動(dòng)態(tài)平衡 貪心算法

一、引言

隨著共享經(jīng)濟(jì)的發(fā)展，在各大公交站臺(tái)，地鐵出入口以及商場、小區(qū)等地區(qū)均有共享單車的投放點(diǎn)，共享單車是一種分時(shí)租賃模式，由企業(yè)自主經(jīng)營，由于其價(jià)格低廉，綠色低碳且短途出行十分方便，受到廣大人民群眾的歡迎。每一輛共享單車都有GPS定位，手機(jī)下載APP能夠隨時(shí)觀測到共享單車的位置，并且某些共享單車企業(yè)會(huì)雇傭員工對(duì)車輛進(jìn)行移位、維護(hù)等服務(wù)，使各個(gè)單車投放點(diǎn)均有一定數(shù)量單車滿足顧客需求且擺放整齊，這對(duì)共享單車投放、調(diào)度起到十分重要的作用。

二、模型的假設(shè)

僅考慮成都市五大主城區(qū)之間的共享單車調(diào)度，且五大主城區(qū)內(nèi)的共享單車總量不變。

不考慮共享單車損毀、故障的情況。

車輛調(diào)度均考慮在凌晨0點(diǎn)到6點(diǎn)之內(nèi)。

每個(gè)投放點(diǎn)既為出發(fā)點(diǎn)又為到達(dá)點(diǎn)。

僅考慮車輛每天早上6點(diǎn)時(shí)的初始狀態(tài)及凌晨12點(diǎn)的末狀態(tài)。

不考慮車輛回到原區(qū)域的情況。

共享單車分配點(diǎn)的數(shù)量始終不會(huì)為負(fù)數(shù)。

三、各區(qū)域共享單車調(diào)度狀態(tài)的確定

各區(qū)域共享單車的分配量即為各區(qū)域共享單車數(shù)量的初始狀態(tài)，經(jīng)過一天的時(shí)間，早上6點(diǎn)到凌晨12點(diǎn)。各區(qū)域的共享單車數(shù)量會(huì)有所變化，則需要對(duì)各區(qū)域的共享單車進(jìn)行調(diào)度。共享單車的調(diào)度狀態(tài)分為兩種，第一種為一天內(nèi)，人對(duì)單車的需求量大于單車的數(shù)量。第二種為一天內(nèi)，人對(duì)單車的需求量小于單車的數(shù)量。根據(jù)各區(qū)域所處的調(diào)度狀態(tài)來制定調(diào)度方案。

首先確定各區(qū)域單車末狀態(tài)的數(shù)量：

由上表可得出如下結(jié)論：

到單車數(shù)量末狀態(tài)時(shí)，1、2、3區(qū)域的單車數(shù)量多于初始狀態(tài)量，而4、5區(qū)域的單車數(shù)量少于初始狀態(tài)量，故需要將1、2、3區(qū)域的單車調(diào)度到4、5區(qū)域。

約束條件：

由之前問題分析可知需要將1、2、3區(qū)域的單車調(diào)度到4、5區(qū)域。

1.從1、2、3區(qū)域調(diào)度出來的單車數(shù)量為車輛末狀態(tài)與初始狀態(tài)的差值。

2.從1、2、3區(qū)域調(diào)度出來到達(dá)4、5區(qū)域的單車數(shù)量為4、5區(qū)域車輛初狀態(tài)與末狀態(tài)的差值。

3.從1、2、3區(qū)域調(diào)度出來的單車數(shù)量與4、5區(qū)域補(bǔ)充的單車數(shù)量一致。

4.從1、2、3區(qū)域出發(fā)僅能選擇一個(gè)目的地。

5.回到4、5區(qū)域的單車的來源是1、2、3區(qū)域調(diào)度的單車。

五、模型求解

經(jīng)過貪心算法得出最佳調(diào)度方案為：先將區(qū)域3的單車調(diào)運(yùn)4.6萬輛到區(qū)域4，然后再將區(qū)域2的單車調(diào)運(yùn)1.5萬輛到區(qū)域4；將區(qū)域3的單車調(diào)運(yùn)1.5萬輛到區(qū)域5，最后將區(qū)域1的單車調(diào)運(yùn)2.3萬輛到區(qū)域5。

六、結(jié)語

在大多數(shù)情況下，單車投放點(diǎn)供求不平衡的情況是十分常見的，所以對(duì)單車進(jìn)行合理地分配與調(diào)度十分重要，這不僅能提高單車的使用效率而且能提高顧客的滿意度，如果方案合理的話還能達(dá)到成本最小化。所以在現(xiàn)實(shí)生活中，對(duì)各個(gè)單車投放點(diǎn)進(jìn)行定期地調(diào)度是十分，必要的，此模型僅提供一定借鑒作用，希望能起到一定的幫助。