基于多目标规划的城市垃圾运输车辆调度问题研究

郭禹+朱大鹏

【摘 要】随着城市化的发展，城市垃圾问题已成为危害城市环境、制约城市发展的顽疾，如何及时高效的转运城市垃圾是目前各大城市面临的严峻挑战。本文针对该问题，运用运筹学的原理建立了垃圾转运车辆调度方案的多目标规划模型，并运用实例分析的形式验证了该模型在减少垃圾车辆运营成本、提高运营效率方面的有效性。

【关键词】 垃圾运输  车辆调度  运营费用  多目标规划

【Abstract】 With the development of city， city garbage transfer hazards has become a city environment，restricting the development of the city. Aiming at this problem， a scheme of vehicle scheduling garbage transfer established principles of operational research （including route scheduling，scheduling time and working mode） multi-objective programming model， and an example is used to analysis the form to verify the validity of the model.

【Keywords】 garbage transport  vehicle scheduling  operating expenses multi-objective programming

1 引言

随着现阶段“绿色城市、健康城市”的观念日益深入人心，人们对城市的发展提出了更高的要求，如何建设“绿色城市、宜居城市”[1][2]使之符合可持续性发展的理念是现阶段城市发展的重中之重，而解决城市垃圾问题更是之题中应有之义。

2 问题提出

假设某城区有个垃圾集中点，第个集中点存放垃圾的数量为吨，运输车辆载重为吨，运输车辆平均速度为千米/小时，每台车每日平均工作时间为小时，运输车辆重载费用为元/吨千米，运输辆车和垃圾装卸铲车空载费用为元/吨千米，第个垃圾集中点的坐标为。如何调度运输车辆，使得总的运营费用最小[3]。

3 数学模型的建立

3.1 模型假设

垃圾只在晚上运输，每天每站的垃圾量不变化;街道方向均平行于坐标轴，车辆可以任意选择路径;运输车到站后必须把该站的垃圾装完;运输车空载与重载速度均为40公里/小时;无塞车状况，车辆运输状况良好;运输车最大超载量不大于0.1吨;运输车的使用数量足够;每台车每天的工作时间不超过4小时。

以垃圾处理厂为坐标原点，建立平面直角坐标系，给出各个垃圾集中点的坐标，则垃圾集中 点到垃圾处理厂的运输距离可表示为（假设街道方向均平行于坐标轴）[4]-[5]。

3.2 符号约定

：序号为站点的垃圾量;：序号为站点的坐标; ：运输车总重载费用;：运输车总空载费用;：运输车总费用;：需用运输车的总车次数;：第辆车出车次数;

3.3 问题分析

由于运营路费是最主要的，车辆安排、路线选择都是为运营路费的最小化提供条件，所以应首先考虑运营路费，之后再考虑车辆安排。为了使运输车运费最小，总的思路是让空载运输车一直开到最远站，在保证时间、重载量有限的前提下，沿途把各站点的垃圾带回。根据这一思路，全部过程运输车的重载费用可表示为：

（1）

从上式中可以看出，运输车的重载费用是恒定的，又由于总运费为重载与空载运费之和，所以总运费的确定就可以转化为满足一定条件下的各车次最远点的选择问题。某车次运输车经过的路径选择应遵循以下原则：一是远者优先原则。某车次最远起始点的选择直接关系到运费多少，所以该车次在沿途返回中应尽量把较远点的垃圾带回;二是不走冤枉路原则。一方面，离远点较远的站点坐标应分别大于离远点较近站点的坐标，在各个坐标上均不走回头路;另一方面，由于在路途相等的条件下，重载费用要比空载费用大的多，因此，尽量让车辆空载跑路，当然在现实中显然不成立。

3.4 模型建立

根据问题分析及假设，运输车费用建立以下数学模型：

重载费用                        （2）

空载费用                       （3）

总费用：                          （4）

满足以下约束要求：

（5）

式（5）为时间约束。

载重量约束：                           （6）

路线约束：                （7）

3.5 实例分析

某市共有36个垃圾集中点，以垃圾处理厂为坐标原点，每个垃圾集中点的坐标及其垃圾量如表1。endprint

垃圾处理场的运输设备及每个垃圾集中点的基本情况如下表2。

根据上述约束条件6知：站点30（28，18）、28（24，20）、36（30，12）首先必须作为某车次的最远点，再结合约束条件4、5，依次选出各车次的次远点，一直到满足约束条件的最大值为之。依次选出各个路线，最后确定出各车次的行走路线如图1所示。

根据上面确定的路线，把各车次所经过的垃圾站数、最远点、所用时间、总载重量进行归纳，计算出各车次运营费用及总费用，如下表3所示。

根据时间约束，最少要派7辆车执行任务，其中把4与11、5与10、6与9、7与8车次分别合并，让4辆车执行任务;其余的3个车次分别派3辆车执行。

考虑到要把司机休息的时间合并到一块，应该把某车辆所执行的两个车次放在一块，做出安排如下表4所示。

在上述模型中，车辆用了7辆，而总运输时间为22.12小时，每天每辆车平均工作时间为3.16小时，车辆安排上还需要修正。下面给出车辆修改模型。

假设（8）中，车辆每天工作时间都不大于4小时，应该修正为每台车几天工作总时间之和除以天数不大于4即可，这样可以进一步满足题目要求。则式（9.4）可以修正为：

（8）

其中：为车辆每天工作天数。

由于，所以最少安排6辆车，安排车辆的总体思路是让工作时间少的与工作时间多的车辆交替轮流担任各车次的运输工作，同时考虑到要把司机休息时间合并到一起，应该把某车辆所执行的两个车次放在一起，尽量使每个车辆满意，做出安排如下表5所示。

以上是对载重量都为6吨的运输车的调度方案。

4 结语

从上述模型中可以看出，运输车辆额定载重量越大、最远点的垃圾数量越少、转运的运营费用就越小。由于垃圾集中点的设置对车辆路线的选择有一定的影响，间接的增加了运营费用。而垃圾集中点的设置又由居民的分布确定的，对垃圾处理厂而言属于不可控因素，因此只有进一步考察运输车辆的型号，才能最大程度的降低运营费用。

参考文献：

[1]陈冠华.北京城市生活垃圾状况预测及效益评价[D].北京：北方工业大学，2009.

[2]曾坚，左长安.基于可持续性与和谐理念的绿色城市设计理论[J].建筑学报，2006（12）：10-13.

[3]李引珍.管理运筹学[M].北京：科学出版社，2012：198-205.

[4]孙宏，杜文，徐杰.最小费用最大流问题在航班衔接问题中的应用[J].南京航空航天大学学报，2001（5）：478-481.

[5]方道元，韦明俊.数学建模——方法引导与案例分析[M].浙江：浙江大学出版社，2011：25-30.endprint

垃圾处理场的运输设备及每个垃圾集中点的基本情况如下表2。

根据上述约束条件6知：站点30（28，18）、28（24，20）、36（30，12）首先必须作为某车次的最远点，再结合约束条件4、5，依次选出各车次的次远点，一直到满足约束条件的最大值为之。依次选出各个路线，最后确定出各车次的行走路线如图1所示。

根据上面确定的路线，把各车次所经过的垃圾站数、最远点、所用时间、总载重量进行归纳，计算出各车次运营费用及总费用，如下表3所示。

根据时间约束，最少要派7辆车执行任务，其中把4与11、5与10、6与9、7与8车次分别合并，让4辆车执行任务;其余的3个车次分别派3辆车执行。

考虑到要把司机休息的时间合并到一块，应该把某车辆所执行的两个车次放在一块，做出安排如下表4所示。

在上述模型中，车辆用了7辆，而总运输时间为22.12小时，每天每辆车平均工作时间为3.16小时，车辆安排上还需要修正。下面给出车辆修改模型。

假设（8）中，车辆每天工作时间都不大于4小时，应该修正为每台车几天工作总时间之和除以天数不大于4即可，这样可以进一步满足题目要求。则式（9.4）可以修正为：

（8）

其中：为车辆每天工作天数。

由于，所以最少安排6辆车，安排车辆的总体思路是让工作时间少的与工作时间多的车辆交替轮流担任各车次的运输工作，同时考虑到要把司机休息时间合并到一起，应该把某车辆所执行的两个车次放在一起，尽量使每个车辆满意，做出安排如下表5所示。

以上是对载重量都为6吨的运输车的调度方案。

4 结语

从上述模型中可以看出，运输车辆额定载重量越大、最远点的垃圾数量越少、转运的运营费用就越小。由于垃圾集中点的设置对车辆路线的选择有一定的影响，间接的增加了运营费用。而垃圾集中点的设置又由居民的分布确定的，对垃圾处理厂而言属于不可控因素，因此只有进一步考察运输车辆的型号，才能最大程度的降低运营费用。

参考文献：

[1]陈冠华.北京城市生活垃圾状况预测及效益评价[D].北京：北方工业大学，2009.

[2]曾坚，左长安.基于可持续性与和谐理念的绿色城市设计理论[J].建筑学报，2006（12）：10-13.

[3]李引珍.管理运筹学[M].北京：科学出版社，2012：198-205.

[4]孙宏，杜文，徐杰.最小费用最大流问题在航班衔接问题中的应用[J].南京航空航天大学学报，2001（5）：478-481.

[5]方道元，韦明俊.数学建模——方法引导与案例分析[M].浙江：浙江大学出版社，2011：25-30.endprint

垃圾处理场的运输设备及每个垃圾集中点的基本情况如下表2。

根据上述约束条件6知：站点30（28，18）、28（24，20）、36（30，12）首先必须作为某车次的最远点，再结合约束条件4、5，依次选出各车次的次远点，一直到满足约束条件的最大值为之。依次选出各个路线，最后确定出各车次的行走路线如图1所示。

根据上面确定的路线，把各车次所经过的垃圾站数、最远点、所用时间、总载重量进行归纳，计算出各车次运营费用及总费用，如下表3所示。

根据时间约束，最少要派7辆车执行任务，其中把4与11、5与10、6与9、7与8车次分别合并，让4辆车执行任务;其余的3个车次分别派3辆车执行。

考虑到要把司机休息的时间合并到一块，应该把某车辆所执行的两个车次放在一块，做出安排如下表4所示。

在上述模型中，车辆用了7辆，而总运输时间为22.12小时，每天每辆车平均工作时间为3.16小时，车辆安排上还需要修正。下面给出车辆修改模型。

假设（8）中，车辆每天工作时间都不大于4小时，应该修正为每台车几天工作总时间之和除以天数不大于4即可，这样可以进一步满足题目要求。则式（9.4）可以修正为：

（8）

其中：为车辆每天工作天数。

由于，所以最少安排6辆车，安排车辆的总体思路是让工作时间少的与工作时间多的车辆交替轮流担任各车次的运输工作，同时考虑到要把司机休息时间合并到一起，应该把某车辆所执行的两个车次放在一起，尽量使每个车辆满意，做出安排如下表5所示。

以上是对载重量都为6吨的运输车的调度方案。

4 结语

从上述模型中可以看出，运输车辆额定载重量越大、最远点的垃圾数量越少、转运的运营费用就越小。由于垃圾集中点的设置对车辆路线的选择有一定的影响，间接的增加了运营费用。而垃圾集中点的设置又由居民的分布确定的，对垃圾处理厂而言属于不可控因素，因此只有进一步考察运输车辆的型号，才能最大程度的降低运营费用。

参考文献：

[1]陈冠华.北京城市生活垃圾状况预测及效益评价[D].北京：北方工业大学，2009.

[2]曾坚，左长安.基于可持续性与和谐理念的绿色城市设计理论[J].建筑学报，2006（12）：10-13.

[3]李引珍.管理运筹学[M].北京：科学出版社，2012：198-205.

[4]孙宏，杜文，徐杰.最小费用最大流问题在航班衔接问题中的应用[J].南京航空航天大学学报，2001（5）：478-481.

[5]方道元，韦明俊.数学建模——方法引导与案例分析[M].浙江：浙江大学出版社，2011：25-30.endprint