基于贪心算法的汽车租赁调度问题研究

叶子琦 张乾元 廖雅昕 张 挺

(重庆邮电大学通信与信息工程学院 重庆 400065)

一、引言

汽车租赁业被誉为“朝阳产业”，是中国新兴的交通运输服务业，也是满足人民群众个性化出行、商务活动需求和保障重大社会活动的重要交通方式。国内汽车租赁市场兴起于1990年，随着市场经济的进一步完善，中国汽车租赁市场迅速发展，各地的汽车租赁公司如雨后春笋纷纷出现。由于科学合理的汽车租赁调度方案对汽车租赁公司的最终经济效益和行业竞争力有重大影响，而行业内对汽车租赁调度还没有成熟且完备的方案，因此，本文的研究方案对汽车租赁公司发展有一定意义。笔者针对某汽车租赁公司的具体情况进行分析，建立单目标优化模型，利用贪心算法得到具体方案。

二、工程需求

某城市有一家汽车租赁公司，年初时有379辆可供租赁的汽车分布在全市的20个代理点中。

由于汽车数量不足，会带来经济损失。同时，各个汽车点的转运成本、短缺的损失也是不可忽略的因素。第一天汽车点的初始布局方式如下：

图1 现有汽车点坐标以及车辆数

要求：

1、综合考虑转运成本、短缺损失和公司获利。

2、给出最终目标，使可持续盈利最大，有利于公司运营。

三、方案设计与实现

由于调度转运只是考虑两点之间的距离连线，而目标是路径最短，因此，有可能出现中间点，使得间接转运较直接转运更近，转运成本更低。

图2 中间点转运的优化举例

因此，本文将采用Floyd算法[1]，对整体路径进行优化。定义任意两代理点间的最小车辆转运代价为：

考虑到调度问题的供需互斥、需车上限原则以及发车限制约束。且代理点由于租车带来收入，使得每个代理点不再只有缺损费，有新的收益函数产生且代理点间的转运费最小目标不变。总收益为总利润减去车辆调度成本和缺车损失，具体收益函数表示如下：

综合上述分析，单目标优化模型可表述为：

为解决上述模型，本文引入贪心算法[2]，进行设计求解，具体步骤如下：

Step1：应用同一规则，将原问题变为一个相似但规模更小的子问题。

Step2：从问题的某一初始解出发，按实际标准，若能朝给定的总目标前进一步就得到可行解的一个解元素，一直重复该步骤直至无解元素。

Step3：由所有解元素组合成问题的可行解。

通过对以上模型的求解，得到如下结果(考虑到结果数据量太大，本文在此只展示部分答案)：

表1 结果调度示意

最终，求解出未来四周总收益可达3954.2053万元，较未优化的3861.4264万元增加了92.7789万元，即总收益优化了2.4%，故此模型下给出了最优盈利的车辆调度方案。

四、结束语

针对某汽车租赁公司的具体汽车分布情况和数量，综合考虑汽车转运成本、短缺损失等影响因素，建立以汽车租赁公司获利最大为目标的优化模型，并利用贪心算法进行求解，最终得到具体调度方案。