葉子琦 張乾元 廖雅昕 張 挺

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

一、引言

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

二、工程需求

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

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

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

要求：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)束語

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