基于貪心算法的汽車租賃調(diào)度問題研究

葉子琦 張乾元 廖雅昕 張 挺

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

一、引言

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

二、工程需求

某城市有一家汽車租賃公司，年初時(shí)有379輛可供租賃的汽車分布在全市的20個(gè)代理點(diǎn)中。

由于汽車數(shù)量不足，會(huì)帶來經(jīng)濟(jì)損失。同時(shí)，各個(gè)汽車點(diǎn)的轉(zhuǎn)運(yùn)成本、短缺的損失也是不可忽略的因素。第一天汽車點(diǎn)的初始布局方式如下：

圖1 現(xiàn)有汽車點(diǎn)坐標(biāo)以及車輛數(shù)

要求：

1、綜合考慮轉(zhuǎn)運(yùn)成本、短缺損失和公司獲利。

2、給出最終目標(biāo)，使可持續(xù)盈利最大，有利于公司運(yùn)營。

三、方案設(shè)計(jì)與實(shí)現(xiàn)

由于調(diào)度轉(zhuǎn)運(yùn)只是考慮兩點(diǎn)之間的距離連線，而目標(biāo)是路徑最短，因此，有可能出現(xiàn)中間點(diǎn)，使得間接轉(zhuǎn)運(yùn)較直接轉(zhuǎn)運(yùn)更近，轉(zhuǎn)運(yùn)成本更低。

圖2 中間點(diǎn)轉(zhuǎn)運(yùn)的優(yōu)化舉例

因此，本文將采用Floyd算法[1]，對(duì)整體路徑進(jìn)行優(yōu)化。定義任意兩代理點(diǎn)間的最小車輛轉(zhuǎn)運(yùn)代價(jià)為：

考慮到調(diào)度問題的供需互斥、需車上限原則以及發(fā)車限制約束。且代理點(diǎn)由于租車帶來收入，使得每個(gè)代理點(diǎn)不再只有缺損費(fèi)，有新的收益函數(shù)產(chǎn)生且代理點(diǎn)間的轉(zhuǎn)運(yùn)費(fèi)最小目標(biāo)不變?？偸找鏋榭偫麧?rùn)減去車輛調(diào)度成本和缺車損失，具體收益函數(shù)表示如下：

綜合上述分析，單目標(biāo)優(yōu)化模型可表述為：

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

Step1：應(yīng)用同一規(guī)則，將原問題變?yōu)橐粋€(gè)相似但規(guī)模更小的子問題。

Step2：從問題的某一初始解出發(fā)，按實(shí)際標(biāo)準(zhǔn)，若能朝給定的總目標(biāo)前進(jìn)一步就得到可行解的一個(gè)解元素，一直重復(fù)該步驟直至無解元素。

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

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

表1 結(jié)果調(diào)度示意

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

四、結(jié)束語

針對(duì)某汽車租賃公司的具體汽車分布情況和數(shù)量，綜合考慮汽車轉(zhuǎn)運(yùn)成本、短缺損失等影響因素，建立以汽車租賃公司獲利最大為目標(biāo)的優(yōu)化模型，并利用貪心算法進(jìn)行求解，最終得到具體調(diào)度方案。