基于貪心算法的汽車租賃調度問題研究

葉子琦 張乾元 廖雅昕 張 挺

(重慶郵電大學通信與信息工程學院 重慶 400065)

一、引言

汽車租賃業被譽為“朝陽產業”，是中國新興的交通運輸服務業，也是滿足人民群眾個性化出行、商務活動需求和保障重大社會活動的重要交通方式。國內汽車租賃市場興起于1990年，隨著市場經濟的進一步完善，中國汽車租賃市場迅速發展，各地的汽車租賃公司如雨后春筍紛紛出現。由于科學合理的汽車租賃調度方案對汽車租賃公司的最終經濟效益和行業競爭力有重大影響，而行業內對汽車租賃調度還沒有成熟且完備的方案，因此，本文的研究方案對汽車租賃公司發展有一定意義。筆者針對某汽車租賃公司的具體情況進行分析，建立單目標優化模型，利用貪心算法得到具體方案。

二、工程需求

某城市有一家汽車租賃公司，年初時有379輛可供租賃的汽車分布在全市的20個代理點中。

由于汽車數量不足，會帶來經濟損失。同時，各個汽車點的轉運成本、短缺的損失也是不可忽略的因素。第一天汽車點的初始布局方式如下：

圖1 現有汽車點坐標以及車輛數

要求：

1、綜合考慮轉運成本、短缺損失和公司獲利。

2、給出最終目標，使可持續盈利最大，有利于公司運營。

三、方案設計與實現

由于調度轉運只是考慮兩點之間的距離連線，而目標是路徑最短，因此，有可能出現中間點，使得間接轉運較直接轉運更近，轉運成本更低。

圖2 中間點轉運的優化舉例

因此，本文將采用Floyd算法[1]，對整體路徑進行優化。定義任意兩代理點間的最小車輛轉運代價為：

考慮到調度問題的供需互斥、需車上限原則以及發車限制約束。且代理點由于租車帶來收入，使得每個代理點不再只有缺損費，有新的收益函數產生且代理點間的轉運費最小目標不變。總收益為總利潤減去車輛調度成本和缺車損失，具體收益函數表示如下：

綜合上述分析，單目標優化模型可表述為：

為解決上述模型，本文引入貪心算法[2]，進行設計求解，具體步驟如下：

Step1：應用同一規則，將原問題變為一個相似但規模更小的子問題。

Step2：從問題的某一初始解出發，按實際標準，若能朝給定的總目標前進一步就得到可行解的一個解元素，一直重復該步驟直至無解元素。

Step3：由所有解元素組合成問題的可行解。

通過對以上模型的求解，得到如下結果(考慮到結果數據量太大，本文在此只展示部分答案)：

表1 結果調度示意

最終，求解出未來四周總收益可達3954.2053萬元，較未優化的3861.4264萬元增加了92.7789萬元，即總收益優化了2.4%，故此模型下給出了最優盈利的車輛調度方案。

四、結束語

針對某汽車租賃公司的具體汽車分布情況和數量，綜合考慮汽車轉運成本、短缺損失等影響因素，建立以汽車租賃公司獲利最大為目標的優化模型，并利用貪心算法進行求解，最終得到具體調度方案。