Management Science and Engineering
Vol.3 No.03(2014), Article ID:14071,7 pages
DOI:10.12677/MSE.2014.33009

Study of City Garbage Transportation Vehicle Scheduling Problem Based on Multiple Objective Programming

Yu Guo, Dapeng Zhu

Lanzhou Jiaotong University, Lanzhou

Email: guoyu0803@sohu

Copyright © 2014 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received: Jul. 4th, 2014; revised: Aug. 5th, 2014; accepted: Aug. 12th, 2014

ABSTRACT

With the development of urbanization, municipal waste has become a serious issue that hazards the municipal environment and constrains the urban development. How to transport the municipal waste in a timely and efficient way is currently a major challenge faced by big cities. Aiming at this issue, this thesis uses the principle of operations research to establish the multi-objective programming model of the vehicle scheduling program for waste transport (including scheduling routes, scheduling time and work mode) and uses the case analysis to verify the effectiveness of this model in reducing operating costs of waste transporting vehicles and improving the operational efficiency.

Keywords:Garbage Transport, Vehicle Scheduling, Operating Expenses, Multi-Objective Programming

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

郭  禹,朱大鹏

兰州交通大学,兰州

Email: guoyu0803@sohu

收稿日期:2014年7月4日;修回日期:2014年8月5日;录用日期:2014年8月12日

摘  要

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

关键词

垃圾运输,车辆调度,运营费用,多目标规划

1. 引言

众所周知,城市人口密集,密集的人口必然会带来大量的生活垃圾。据不完全统计,仅北京市一天生活垃圾的生产量大概是5000吨左右,其中不可回收的厨房垃圾大约占37%,这个数字在夏季可能会达到7000吨以上。而且这仅仅指生活垃圾一项,还不包括生产垃圾、办公垃圾、旅游垃圾以及其他垃圾[1] 。大量的垃圾如果不能及时转运和处理不仅污染环境,而且严重影响了人们的生活质量。因此城市垃圾如何转运与处理已成为人们所面临的主要城市问题之一。随着现阶段“绿色城市、健康城市”的观念日益深入人心,人们对城市的发展提出了很高的要求,如何建设“绿色城市、宜居城市”[2] 使之符合可持续性发展的理念是现阶段城市发展的重中之重,而解决城市垃圾问题更是之题中应有之义。

目前几乎所有的城市中都建有很多垃圾集中点,由环保人员将分散在各个场所的垃圾收集起来在垃圾集中点暂时分类存放,而垃圾处理厂每天需要派遣专门的垃圾转运车辆将分散在城市各个集中点的垃圾运回处理厂集中处理。由于每个城市垃圾集中点分布的情况不同以及各个集中点存放垃圾的数量和种类不同,如如何合理的调度运输车、减少车辆空驶、缩短车辆行驶距离、提高车辆效率已经成为每个垃圾处理厂所面临的的主要问题。

2. 问题提出

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

3. 数学模型的建立

3.1. 模型假设

1) 垃圾只在晚上运输,每天每站的垃圾量不变化;

2) 街道方向均平行于坐标轴,车辆可以任意选择路径;

3) 运输车到站后必须把该站的垃圾装完;

4) 运输车空载与重载速度均为40公里/小时;

5) 无塞车状况,车辆运输状况良好;

6) 运输车最大超载量不大于0.1吨;

7) 运输车的使用数量足够;

8) 每台车每天的工作时间不超过4小时。

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

3.2. 符号约定

:序号为站点的垃圾量。

:序号为站点的坐标。

:运输车总重载费用。

:运输车总空载费用。

:运输车总费用。

:需用运输车的总车次数。

:第辆车出车次数。

3.3. 问题分析

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

(1)

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

3.4. 模型建立

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

重载费用

(2)

空载费用

(3)

总费用:

(4)

满足以下约束要求:

(5)

式(5)为时间约束。

载重量约束:

(6)

路线约束:

(7)

3.5. 实例分析

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

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

Table 1. Garbage centralized point coordinate table

表1. 垃圾集中点坐标表

Table 2. Statistics of transportation

表2. 运输情况统计表

根据上述约束条件(9.6)知:站点30(28,18)、28(24,20)、36(30,12)首先必须作为某车次的最远点,再结合约束条件(9.4)、(9.5),依次选出各车次的次远点,一直到满足约束条件的最大值为之。依次选出各个路线,最后确定出各车次的行走路线如图所示:

第一次运输车返回路线:

第二次运输车返回路线:

第三次运输车返回路线:

第四次运输车返回路线:

第五次运输车返回路线:

第六次运输车返回路线:

第七次运输车返回路线:

第八次运输车返回路线:

第九次运输车返回路线:

第十次运输车返回路线:

第十一次运输车返回路线:

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

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

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

Table 3. The train transportation

表3. 各车次运输情况

所示。

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

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

(8)

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

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

车辆工作流程图如下图所示:

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

4. 结束语

通过上述实例分析可知,本文建立的垃圾转运车辆调度模型是有效的。本文模型是从实际生活中抽象出来的理想化模型,具有一定的现实意义。实际问题中可能需要考虑的因素更多,都可以通过构造一

Table 4. Train replacement table

表4. 车次更换情况表

Table 5. Vehicle arrangement and train number replacement

表5. 车辆安排与车次序号更换情况

个恰当的网络(即赋权图)或有向网络,将问题转化成TSP问题或寻找最佳H路的问题,再用合适的方法求出近似最优解或最优解,问题便可迎刃而解。问题的关键就在于如何构造一个有效的网络,在实际问题中应具体问题具体分析。从上述模型中可以看出,运输车辆额定载重量越大,最远点的垃圾数量越少,转运的运营费用就越小。由于垃圾集中点的设置对车辆路线的选择有一定的影响,间接的增加了运营费用。而垃圾集中点的设置是由居民的分布确定的,对垃圾处理厂而言属于不可控因素,因此只有进一步考察运输车辆的型号,才能最大程度的降低运营费用。选择什么样的运输车辆型号,以及如何合理配置现有不同型号的运输车辆从而进一步控制运营成本将是后续研究的方向。

参考文献 (References)

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

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

  3. [3]   李引珍 (2012) 管理运筹学. 科学出版社, 北京, 198-205.

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

  5. [5]   方道元, 韦明俊 (2011) 数学建模——方法引导与案例分析. 浙江大学出版社, 杭州, 25-30.

期刊菜单