基于貪心算法的共享單車的優化調度模型

盧泗化 李倩文

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

關鍵詞：調度模型 供求不平衡 動態平衡 貪心算法

一、引言

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

二、模型的假設

僅考慮成都市五大主城區之間的共享單車調度，且五大主城區內的共享單車總量不變。

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

車輛調度均考慮在凌晨0點到6點之內。

每個投放點既為出發點又為到達點。

僅考慮車輛每天早上6點時的初始狀態及凌晨12點的末狀態。

不考慮車輛回到原區域的情況。

共享單車分配點的數量始終不會為負數。

三、各區域共享單車調度狀態的確定

各區域共享單車的分配量即為各區域共享單車數量的初始狀態，經過一天的時間，早上6點到凌晨12點。各區域的共享單車數量會有所變化，則需要對各區域的共享單車進行調度。共享單車的調度狀態分為兩種，第一種為一天內，人對單車的需求量大于單車的數量。第二種為一天內，人對單車的需求量小于單車的數量。根據各區域所處的調度狀態來制定調度方案。

首先確定各區域單車末狀態的數量：

由上表可得出如下結論：

到單車數量末狀態時，1、2、3區域的單車數量多于初始狀態量，而4、5區域的單車數量少于初始狀態量，故需要將1、2、3區域的單車調度到4、5區域。

約束條件：

由之前問題分析可知需要將1、2、3區域的單車調度到4、5區域。

1.從1、2、3區域調度出來的單車數量為車輛末狀態與初始狀態的差值。

2.從1、2、3區域調度出來到達4、5區域的單車數量為4、5區域車輛初狀態與末狀態的差值。

3.從1、2、3區域調度出來的單車數量與4、5區域補充的單車數量一致。

4.從1、2、3區域出發僅能選擇一個目的地。

5.回到4、5區域的單車的來源是1、2、3區域調度的單車。

五、模型求解

經過貪心算法得出最佳調度方案為：先將區域3的單車調運4.6萬輛到區域4，然后再將區域2的單車調運1.5萬輛到區域4；將區域3的單車調運1.5萬輛到區域5，最后將區域1的單車調運2.3萬輛到區域5。

六、結語

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