摘 要 车辆路径与调度问题(Vehicle routing and scheduling problem, VRSP) 是制造系统自动化和商业服务系统优化调度要解决的重要问题, 常常以路径最短或成本(时间)最小为优化目标. 在强制性碳排放政策的影响下, 如何通过路径优化与调度实现系统的节能减排, 已经成为管理者一个优化控制的目标. 本文建立了针对接送机场服务中以最小碳排放量为目标的车次分配与调度问题的0-1混合整数规划模型, 采用了改进的基于时间和地域划分的极线扫描算法. 重点通过不同类型、规模测试实例, 分别从测试实例的顾客点位置分布、顾客规模以及车辆容量大小、满意度水平分析了对人均碳排放的影响程度, 对现实接送机场服务运作中车辆配置和设置服务水平提供了有价值的建议.
关键词 接送机场服务, 车辆路径与调度问题, 碳排放量, 优化调度, 时间窗
Minimizing Carbon Emissions for Vehicle Routing and Scheduling in Picking upand Delivering Customers to Airport Service
Abstract Vehicle routing and scheduling problem (VRSP) is the important problem in manufacturing systems automa-tion and business services, which often aims at the shortest path or the minimal cost for the optimization and managementobjectives. Under the mandatory carbon emissions policy, there is another important objective for the managers to reducecarbon emissions by optimizing the transport paths of the logistics. In this paper, a 0-1 mixed integer programmingmodel is proposed to minimize carbon emissions for the airport shuttle service. An improved NPFDS algorithm with thepartition from both time and geographical is proposed. Using di®erent type and size test cases, this paper analyzes thefuel consumption per person that is from four respective dimensions, which are the customer position distribution, thecustomer scale, the vehicle capacity and the customer satisfaction degree. Some conclusions and references for the airportshuttle service con¯guration and service degree setting are also obtained.
Key words Pick up to airport service, vehicle routing and scheduling problem (VRSP), carbon emissions, optimaloperation, time windowsCitation
　　车辆路径与调度问题(Vehicle routing and scheduling problem, VRSP)[1¡5]是制造系统自动化和商业服务系统运作管理要解决的基本问题.VRSP是指在满足一定的约束条件下, 合理组织车辆数量、车辆的行车路线和时间等, 依次访问在给定区域范围内具有服务需求和服务时间的顾客点, 以实现系统的最优目标. 这些目标包括成本最小、路径距离(时间)最短、效益或顾客满意度最大等. 该问题广泛存在于制造系统中的车辆自动导引(Automated guided vehicle, AGV)、集成电路布线、机器人加工路径规划、物流配送与分销服务中的集送货服务、校车巴士服务、城市垃圾与危化物品运输等领域. VRSP 包括两个子问题, 即从空间的角度{车辆路径问题(Vehicle routing problem, VRP)和时间的角度{车辆调度问题(Vehicle schedulingproblem, VSP).在学术研究层面, 主要侧重于研4期 杨培颖等: 面向最小碳排放量的接送机场服务的车辆路径与调度 425究考虑时间窗的车辆路径与调度问题(VRSP withtime windows, VRSPTW), 扩展的因素包括多车场、需求可拆分、集送结合、开放/闭环、混合车辆容量、信息及时更新(随机需求) 等. 在对这些问题的优化建模中, 车辆路径与调度问题的优化目标常常是路径最短、成本最小或者时间周期最短. 在强制性碳排放政策影响下, 控制与调度领域中如何通过车辆分配与调度的优化实现节能减排, 还是一个亟待解决的问题. 目前对于车辆碳排放的研究多是从不同类型车辆碳排放量的建模和测定的视角进行研究[6¡8], 而对车辆分配与调度问题的碳排放研究工作很少, 截至目前只有很少的几篇文献. 其中,Figliozzi[9]对具有时间依赖的车辆路径问题(Time-dependent VRP, TDVRP)进行了初步的碳排放的建模. Bektas 等[10]对车辆路径问题进行了建模, 但是因为他只考虑了货物运输, 对于运载对象是人的诸多特点并没有进行考虑, 并且他在求解的时候只考虑了小规模顾客点问题, 这就使得建模的应用受到了局限.
　　目前的研究无论是VRP还是VSP,或是少见的VRSP都是针对理想状况, 没有考虑服务对象的特征属性、配送的环境要求、服务对象(顾客)的需求特征, 因而建立的模型只是一种现实情况的近似.本文的研究背景是面向城市的以人为对象的票务公司接送机场服务. 作为服务型企业的航空票务公司,为了提升企业竞争力, 推出了接送顾客到机场的服务(简称\接送机场服务"). \接送机场服务"提高了顾客的服务满意度, 进而增强了市场竞争力, 提升了市场占有份额, 它已成为航空票务公司企业的一项重要增值服务内容和运营手段. Tang 等[11¡12]以一些传统的目标(如: 成本最小、顾客满意度最大等)对航空公司接送机场服务问题进行了研究. 但是, 在强制性碳排放政策影响下, 如何通过运输路径的优化实现节能减排, 不仅是建设资源节约型和环境友好型城市的需要, 也是应对全球气候变化的重要举措, 这已经成为管理者另一个重要的优化目标.本文在分析接送机场服务运作模式和服务对象特征的基础上, 首次从碳排放视角建立了以降低运营过程中车辆碳排放总量为目标的非线性0-1混合整数规划模型; 提出了改进的基于时间和地域划分的极线扫描算法, 分别从四个方面, 即顾客点位置分布、顾客规模、车辆容量大小、满意度水平分析了对人均碳排放量的影响程度, 其结论对现实接送机场服务运作中车辆配置和设置服务水平提供了有价值的建议
　　.1 车辆碳排放量的影响因素及计算公式
　　1.1 影响因素
　　汽车的碳排放来自于消耗的燃料. 目前, 我国机动车的燃料消耗效率水平普遍比世界发达国家低10 %»20 %,这说明我国汽车领域的节能减排还有很大的空间. 影响燃油消耗的因素很复杂, 概括起来主要包括三类: 汽车设计技术参数因素、汽车使用环境因素、驾驶员工作状态与行为习惯因素. 在汽车设计技术参数状况方面, 又可以分为: 发动机的压缩比和发动机功率, 汽车的滚动阻力、坡道阻力和加速阻力等. 对于指定车型, 以上因素都是非可控的固定因素. 整车质量(空车质量+负载质量)的大小也会影响到耗油量, 因为负载质量是可变的, 所以这个因素为人为可控因素. 在汽车使用环境方面, 汽车行驶道路的状况、海拔、风力、风向、气温等因素, 对汽车燃料的消耗都有一定的影响. 对于指定的行驶环境, 这些因素是非可控的固定因素. 在驾驶员的工作状态与行为习惯因素方面, 汽车在行驶过程中, 受驾驶员的控制, 对于同一目的地, 不同的驾驶员驾驶习惯不同, 会导致选择道路不同(距离不同)、车辆速度不同、刹车次数不同, 这些方面都对耗油量有显著的影响. 同时, 这个因素也被认为是人为可控因素.
　　1.2 计算公式
　　综合以上分析, 在固定车型、指定行驶环境条件下, 对于耗油量的计算, 要考虑非可控固定因素和人为可控因素的影响. 国外的研究者们对如何利用这些因素构建碳排放模型, 测定碳排放量也进行了一定的研究[13¡15]. 本文参考了文献[10, 16], 对现有的数据分析化简得到发动机的有效功率(即牵引功率)为Pt, 计算如下:Pt =Mav+Mgvsinµ+ 0:5CdA½v3+MgV Crcosµv (1)其中, M表示空车质量与负载质量的总和, v表示汽车行驶速度(单位: m/s), a表示汽车行驶加速度(单位: m/s2), g表示重力加速度常量(9.81 m/s2),µ表示所经过道路的倾角, A表示汽车正面表面积(单位: m2),½表示空气密度(单位: kg/m3),Cd 和Cr 分别表示牵引力系数和滚动阻力系数. 式(1) 表示, 牵引功率由速度、倾角阻力、空气阻力和摩擦阻力等部分构成.为了简单而不失一般性, 假定车辆行驶在给定的路线上时, 所有的参数是常量, 但因每个顾客点接送人数可以不同, 所以负载可变. 在顾客点i 和顾客点j 之间, 汽车有效功可以近似的表达为Pij tPt(dij=vij)t®ij(wij +fij)dij +¯ijv2ijdij(2)其中, ®ij =a+gsinµij +gCrcosµij 是给定路径(i; j)上的特定常量; ¯ij= 0:5CdA½是给定车型的特定常量. 式(2) 可以近似求得给定车型在给定两426 自 动 化 学 报 39卷个点(i; j) 之间的汽油热效能(单位: J), 进而可以求出相应的含碳气体的排放量. dij 表示给定两个点(i; j)之间的距离, vij 表示给定两个点(i; j)之间的速度, wij 表示空车质量(因指定情况下, 空车质量可认为是固定量, 所以后文wij 用w代替),fij 表示负载质量, 则®ij(wij +fij)dij 代表承载车重及负载所需要的能量需求, ¯ijv2ijdij 代表相应速度的能量需求. 因此, 对于指定车型和行驶环境, 考虑优化碳排放的影响主要从优化三种人为可控因素(承载车重及负载所需要的能量需求, 车辆行驶路径、车辆行驶速度等几个方面)入手, 不考虑行驶速度的变化因素, 汽油发动机的热效率约取20 %»30 %.
　　2 车辆分配与调度问题的最小碳排放量模型
　　2.1 问题描述
　　以最小碳排放量为目标的接送机场服务的核心科学问题是车次分配与调度问题(Vehicle alloca-tion and scheduling problem, VASP), 即需要多少辆车、哪个车次接送哪些位置的哪些顾客、每个车次接送顾客的顺序如何、车次的发车时间如何安排,通过合理配置达到碳排放最小的目标. 该问题是车辆路径与调度问题(Vehicle routing and schedulingproblem, VRSP)的一个子类, 但有别于传统的物流配送问题, 它是以降低碳排放量为主要目标的以人为配送对象的一种新型物流运作模式与理念, 而且比一般的车辆路径与调度问题更为复杂, 这种复杂性体现在: 1) 配送对象(乘机顾客)行为的复杂性(接送时间松紧要求、绕行限制要求、出行行为习惯等); 2) 顾客量的规模大, 以沈阳市为例, 日均顾客量约为1 000; 3)碳排放量影响因素的定性分析与定量描述以及低碳模型的构建.2.2 问题假设本文将同一位置并有相同乘机时间要求的顾客看成一个整体顾客点. 为了能够清楚地描述问题, 做如下假设:1)只有一个发车中心, 只有一个机场;2)相同顾客点有同一时间要求的, 看作一个顾客点, 相同顾客点有不同时间要求的, 看作不同顾客点;3)将一个顾客点的所有顾客看作一个整体, 即不可分割, 同时假设每个顾客点的顾客人数不大于车辆承载能力;4)接送车辆为同一车型, 数量足够多; 车辆容量为定值;5)整个接送过程是匀速行驶, 道路平整, 路面倾角, 准时制服务, 忽略上下车时间.
　　2.3 符号表示
　　在一个计划周期内, 用U表示工作计划的时间范围, 取早6:00到晚8:00. G=fN; Arcg 表示由节点和节点间边所构成的网状结构图; 其中:N=f0;1;¢ ¢ ¢ ; n + 1g为节点集, 0 表示车场中心,n+ 1表示机场, N0=f1;2;¢ ¢ ¢ ; ng为顾客点集合;Arc=f(i; j); i 2N; j2Ng表示发车场、顾客点和机场之间边的集合; 顾客点i(i2N0)有一个接车时间范围[ei; li]; 该顾客点的顾客人数为qi; 车辆容量约束为Q; °是模型求解设定的顾客可接受的满意度水平值; ti 是车辆到达顾客点i 的时间; S(ti)表示顾客点i 的平均满意度水平; R=f1;2;¢ ¢ ¢ ; rg表示车辆集合; 车辆r(r2R)的发车时间是tsr; 到达机场时间是tar; Tij 表示经过路径(i; j)2Arc的行驶时间; dij 表示路径(i; j)的长度; c表示发动机做功一焦耳的碳排放量; ± 表示服务的绕行系数, 即顾客接受接送机场服务上车到抵达机场所用时间与顾客自行直达机场所用时间之比; fijr 表示第r 辆车在路径(i; j)间的负载; xir 和zijr 是0-1变量, 是对车辆r 所做的决策变量; 当顾客点i 由车次r 接送时, xir= 1;当车次r在经过路径(i; j)2Arc时,zijr= 1.
　　2.4 车辆分配与调度问题的最小碳排放量模型车辆碳排放量通过车辆发动机的有效功(式(2))来计算, 具体如下:mincXr2RX(i;j)2Arc(®ijdijwzijr+®ijfijrdijXk2Nz0kr+dij¯v2zijr) (3)式(3) 表示一个计划周期内所有车辆r 2R发动机做出有效功而产生的碳排放量之和最小; 其中, 系数c 表示发动机做功(单位: J) 的碳排放量; ®ijdijwzijr +®ijfijrdijPk2Nz0kr 表示路径(i; j) 2Arc上承载车的车重w及负载fijr 所需要的能量需求, 即发动机所需做有效功的数值;dij¯v2zijr 表示相应路径上对应速度v的能量要求.在接送机场服务中, 顾客关心服务质量, 因此将顾客的满意度水平作为服务质量指标, 并作为接送机场服务中车次分配与调度模型的满意度约束. 在一般的VRPTW问题中, 时间窗通常被用来表示顾客的需求时间范围, 它可以分为硬时间窗和软时间窗[17].一般的处理方法是将硬时间窗范围作为不可违反的约束条件, 而对软时间窗的违反作为对目标函数的惩罚. 本文以顾客点i 指定的接送时间[ei; li] 为软时间窗, 如果车辆在此范围内到达接送顾客, 顾客将会非常满意, 那么此时的满意度即为100 %. 这里的\软时间窗"和\硬时间窗"的定义是针对是否可以突破约束而言, 软时间窗可以突破约束, 即允许一定范围的违反(Violation); 反之, 硬时间窗则不可违反, 即接送顾客不能超过的时间范围的边界, 如图14期 杨培颖等: 面向最小碳排放量的接送机场服务的车辆路径与调度 427所示[e0i; l0i] 即为顾客点i 的硬时间窗. 如果车辆到达顾客点的时间太早或太晚对于顾客来说都是不可接受的, 所以对于顾客点i 的顾客, 车辆到达的时间不能超过硬时间窗[e0i; l0i], 显然[ei; li] µ[e0i; l0i]. 这里用一个分段线性函数S(ti)来将满意度定量化, 称其为满意度函数[12], 描述如下:S(ti) =8><>:1; ti 2[ei; li]e0i¡tie0i¡ei; ti 2[e0i; ei]l0i¡til0i¡li; ti 2[li; l0i]0; ti6= [e0i; l0i](4)函数图像如图1所示.低碳模型的各个约束如下:S(ti)¸°;8i2N0(5)Xi2N0qiXj2N0[f0gzjir ·Q;8r2R (6)Xr2Rxir= 1; 8i2N0(7)Xr2RXj2N0[f0gzjir= 1; 8i2N0(8)Xr2RXj2N0[fn+1gzijr= 1; 8i2N0(9)tar¡ti ·±Ti(n+1); 8i2N0(10)(tj ¡tsr¡T0j)z0jr= 0; j 2N0; r 2R (11)(tj ¡ti ¡Tij)zijr= 0; i; j 2N0; r 2R (12)(tar¡ti¡Ti(n+1))zi(n+1)r= 0; j2N0; r2R (13)z(n+1)0r =Xj2N0z0ir; i 2N0; r 2R (14)0< tsr; ti; tar< U; i2N; r2R (15)xir; zjir2 f0;1g;(i; j)2Arc; i2N; r2R(16)Xj2N0[f0gzjir =xir; i 2N (17)Xj2Nfjir¡Xj2Nfijr =qi; 8i2N0(18)qizijr ·fijr ·(Q¡qj)zijr;(i; j)2Arc; i2N; r2R (19)式(5) 保证顾客满意度水平的约束; 式(6) 是车辆容量约束; 式(7) 表示每个顾客点的顾客只由一辆车接送; 式(8) 和式(9) 表示车辆在各个位置点之间的流动关系[18¡19]; 式(10) 是绕行时间约束; 式(11)»(13)表示接送过程中车辆在各位置点时间差的准确性; 式(14)表示车辆必然会由机场返回车场;式(15)保证所有计划时间安排在工作计划的时间范围内; 式(16)是决策变量的取值范围; 式(17)表示Zijr 与Xir 之间的转换关系; 式(18)表示每个顾客点的顾客被一次接送完毕; 式(19)表示车辆负载总重量的约束条件.图1 顾客对接送时间的满意度函数Fig. 1 Satisfaction degree function of pickuptime for customers
　　3 最近点优先的双向极线扫描
　　启发式算法接送机场服务的车次分配与调度问题为VR-SPTW的子问题, 而VPSPTW为NP难问题, 因此对于中等规模及以上的问题, 在合理的时间内很难得到精确解. 为此, 我们设计开发了最近点优先的双向极线扫描启发式算法(Nearest point ¯rstdouble-sided sweep algorithm, NPFDS).
　　3.1 种子顾客点的选取定义
　　1 (剩余可用时间twwii). 车辆到达顾客点i之后, 等待该点顾客上车的等待时间.每个需要接送的顾客点都有一个等待车辆接送的时间区间(即软时间窗[17]), 假设一辆车在时间t0由车场发车去接顾客, 任意一个顾客点i(i2N0)的顾客在其软时间窗[ei; li] 的中点时刻上车, 那么该车到达顾客点i 时, 还需要等待时间twi才能接到该点的顾客, 如式(21):twi=ei +li2¡µt0+d0iv¶(20)其中, d0i 表示车场到顾客点的距离, v表示车速. 车辆在时间t0 由车场发车去接顾客点i 产生的等待时间twi. 显然在[0, twi] 的时间区间内, 车辆可以去接其他顾客之后再来接i 点顾客.从剩余可用时间的求值公式可以看出, 该时间值越小, 留给接送车辆的时间越少, 该顾客点需要优先服务的迫切度越大. 由此, 给出定义2.定义2 (第一个种子顾客点). 所有顾客点中剩余可用时间twi最小的一个.例如, 两个顾客点1和2,等待接送车的时间区间分别是1为[9:10, 9:30], 2 为[9:30, 9:50], 发车中心、1、2三点之间的车程分别是d01= 20分钟,428 自 动 化 学 报 39卷d02= 30分钟, d12= 20分钟. 若车辆在9:00开始进行接送服务, 依据定义1可知: tw1= 0,tw2= 10分钟. 依据定义2选取第一个种子顾客点为1顾客点, 接送之后可再接2顾客点. 如果先接2顾客点,则需要另外派车接送1顾客点, 车次的增加将导致碳排放量的增加.
　　3.2 算法思想描述
　　依据第3.1节内容, 可选出第一个种子顾客点.在考虑时间窗、载客数量、道路特点等约束的前提下, 从节能低碳角度来看, 司机接到一个顾客点的顾客后, 如果就近接送另一个顾客是一种合理的行为方式. 本文提出的最近点优先的方法(NPFDS) 即是一种寻找\最近点"的方法. 此处\最近点"是指加入该点后整个车程碳排放量最小的顾客点.当车辆接送完第一个顾客点后, 以第一个接送顾客点为基准点, 从车场到该点的射线顺时针进行区域扫描, 扫描到第一个符合接送要求的顾客点, 记录选择此接送点为下一个接送点时对整个车程碳排放量的影响; 接着, 以从车场到该点的射线逆时针进行区域扫描, 当扫描到第一个符合接送要求的顾客点时, 记录选择此接送点为下一个接送点时对整个车程碳排放量的影响; 比较接送这两个顾客点的碳排放量, 选碳排放量最小的一个顾客点作为第二个顾客点. 以此类推, 直至该车辆无可接顾客点.定义3 (其他种子顾客点). 以前一个种子顾客点为基准, 双向扫描后得到的碳排放量最少的顾客点.一个以最小碳排放量为目标的NPFDS算法选择其他种子顾客点的实例(如图2): 设车重为w, 每个顾客的重量为m0, 车速为v. 选择其他种子顾客点的过程可描述为:1)假设经过之前选择的路径, 到达\当前位置A",此时车上载客量为n0, 接送车到达当前位置耗油P0.2)以从车场到A点的射线顺时针方向进行区域扫描, 扫描到第一个符合接送要求的顾客点B, A与B距离是dab, B距离机场的距离是db(n+1), B顾客点的人数是n1, 计算A经过B点后到机场的碳排放量增量, 用符号CEab 表示.3)以从车场到A点的射线逆时针方向进行区域扫描, 扫描到第一个符合接送要求的顾客点C, A与C的距离是dac, C距离机场距离是dc(n+1), C顾客点的人数是n2, 计算A经过C点后到机场的碳排放量增量, 用符号CEac 表示.4)比较CEab 和CEac 中碳排放量最小的那个顾客点, 作为车辆经过A点后选择得到的其他种子顾客点.图2 算法示意图Fig. 2 Diagram of algorithm4 测试实例与模型参数分析4.1 测试实例及测试环境参数本文采用顾客点分布类型对实例进行分类, 将顾客点分为三种分布类型[20]: 1) 随机分布类型, 即R类实例; 2) 聚类分布类型, 即C类实例; 3) 随机{聚类分布类型, 即RC类实例.1)随机分布实例, 即R类实例, 如图3所示. 这种实例的特点是顾客点随机出现在服务区域内, 无规律可言, 实例命名规则为R+实例规模, 如1 000个顾客点的随机分布实例, 命名为R1000;2)聚类分布实例, 即C类实例, 如图4所示.这种实例的特点是顾客点聚集在几个小群落, 实例命名规则为C+实例规模, 如1 000个顾客点的聚类分布实例, 命名为C1000;图3 随机分布实例R1000Fig. 3 InstanceR1000 of random distributing instances图4 聚类分布实例C1000Fig. 4 InstanceC1000 of cluster distributing instances3)随机{聚类分布实例, 即RC类实例, 如图54期 杨培颖等: 面向最小碳排放量的接送机场服务的车辆路径与调度 429所示. 这种实例综合以上两种实例的特点, 实例命名规则为RC+实例规模, 如1 000个顾客点的随机{聚类分布实例, 命名为RC1000.图5 随机{聚类分布实例RC1000Fig. 5 InstanceRC1000 of random-cluster distributinginstances对每类实例分别随机产生了60、80、100、120、150、200、400、600、800、1 000 个顾客的10 种规模实例, 其中100个顾客以内的实例为小规模实例, 100»600个顾客的实例为中等规模实例, 超过600 个顾客为大规模实例. 每种规模的实例,分别测试了5 种顾客满意度水平下限, 即° =80 %、85 %、90 %、95 %、100 %. 分别选取四种车辆容量(包括司机), 即5人(小轿车)、10人(商务)、15人(小巴)、20人(中巴) 进行测试. 为便于比较, 设定模型基准参数为: 车辆容量为5,满意度水平下限为85 %,基准测试实例为R200.在Intel Atom N270 (1.6 G), 1 G DDR2 Mem-ory, Slackware Linux 13.0, gcc 4.3.3 + glibc 2.9+ make 3.81的计算环境下, 依照车辆类型, 根据相关资料, 选取牵引力系数Cd= 0:45;滚动阻力系数Cr= 0:015;汽车正面表面积A= 1 m2; 空气阻力为1.225 kg/m3. 根据车辆速度在50»70 km/h匀速行驶时, 车辆耗油量最小[21¡22]. 本文选取车速为60 km/h,每名乘客加行李总质量为100 kg.由于碳排放量直接反映在车辆耗油量上, 本文以人均耗油量为比较分析的基准. 本节从实例的顾客点位置分布、顾客规模、顾客满意度水平和车辆容量四个方面共测试实例600组实例, 并分析这些因素对人均耗油量的影响(本文耗油量指车辆有效功的耗油量, 不包含汽车辅助配件如空调、音响等耗油量).4.2 顾客位置分布对人均耗油量的影响为了测定位置分布对人均耗油量是否有影响,选择顾客规模分别为60、200、800 的R类、C类和RC类实例进行了测试. 测试实例中以车辆容量5人为例, 不同满意度水平下的人均耗油量计算结果如表1所示. 表中的数值是以R类实例为基准\1",C类和RC类实例的人均耗油量为相对值, 例如规模为60人的R类实例, 满意度水平为80 %时, 同规模C类实例和RC类实例的耗油量分别为R类实例的0.6倍和1.01倍, 其他同理.表1 顾客点位置分布对人均耗油量的影响(Q= 5)Table 1 In°uence of customer location distribution forper capita fuel consumption (Q= 5)实例 0.8 0.85 0.9 0.95 1C60 0.60 0.95 0.97 1.14 1.21R60 1.00 1.00 1.00 1.00 1.00RC60 1.01 1.02 1.03 1.31 1.26C200 0.97 0.99 1.02 1.08 1.02R200 1.00 1.00 1.00 1.00 1.00RC200 1.03 1.04 0.99 0.94 0.94C800 1.03 1.03 1.00 0.97 0.97R800 1.00 1.00 1.00 1.00 1.00RC800 1.02 1.02 1.01 1.03 1.01图6表示不同车辆容量下顾客点规模为60人时, 人均耗油量在三种顾客位置分布情形下随顾客满意度水平下限变化的曲线. 通过图6可以得出, 不同位置分布类型的实例会导致人均耗油量不同, 对于小规模顾客人数, 满意度水平小于95 %时并无明显耗油量规律性的变化; 在满意度大于95 %,RC类实例会表现为较多的耗油量, C类次之, R类最少.对于车辆容量取其他值时, 计算可得到类似结论. 综上, 顾客位置分布类型对人均耗油量虽有影响, 但并不显著.图6 车辆容量为5时不同位置分布人均耗油量随顾客满意度水平变化曲线Fig. 6 Per capita fuel consumption curves of di®erentposition distribution with the customer satisfaction level(Q= 5)4.3 车辆容量对人均耗油量的影响分别采用比较典型的R类实例和C类实例来说明车辆容量Q= 5; Q = 10; Q = 15; Q = 20四种情况对人均耗油量的影响. 表2给出了满意度水平为85 %时, R类实例不同顾客规模时, 车辆容量变化对耗油量的影响. 表中每个实例规模都以车辆容量5人为基准\1",其他车辆容量为相对Q= 5的人均耗油量比值; 例如对于实例R60,车辆容量为10人, 15 人的耗油量分别为车辆容量为5人的人均耗油量的0.88倍和0.84倍, 其他同理.430 自 动 化 学 报 39卷图7表示不同车辆容量下C类实例随顾客规模变化的曲线(°= 85 %).从表2和图7中可以发现:随着车辆容量的增大, 人均耗油量减少; 当车辆容量增加到一定程度, 如容量为15和20时, 耗油量几乎趋同, 说明车辆容量15为最合适的车型.图7 不同车辆容量下C类实例随顾客规模变化的曲线(°= 85 %)Fig. 7 Per capita fuel consumption curves of di®erentvehicle capacity with the number of customers based onclassC( °= 85 %)表2 R类实例不同规模情况下车辆容量对人均耗油量的影响(°= 85 %)Table 2 In°uence of di®erent vehicle capacity for percapita fuel consumption based on classR(°= 85 %)车辆容量 60 200 600 800 1 0005 1.00 1.00 1.00 1.00 1.0010 0.88 0.79 0.68 0.67 0.6415 0.84 0.76 0.65 0.63 0.5920 0.84 0.76 0.65 0.64 0.594.4 满意度水平对人均耗油量的影响分别采用比较典型的R类实例和C类实例说明满意度水平对人均耗油量的影响, 分别选取了满意度水平80 %, 85 %, 90 %, 95 %, 100 %五档进行测试. 表3给出了R类实例在相同车辆容量下不同满意度水平对人均耗油量的影响. 表中, 每个实例都以满意度水平°= 85 %为基准\1",其他满意度水平分别为基准水平的相对值, 如对实例R60,满意度水平为95 %和100 %时的人均耗油量分别为满意度水平85 %时人均耗油量的1.16倍和1.83倍, 其他同理.图8表示C类不同规模实例下满意度水平对人均耗油量的变化曲线. 通过图8和表3可发现: 无论对于C类还是R类实例, 随着满意度的增加, 人均耗油量都增加; 满意度水平95 %时的耗油量几乎为满意度水平85 %时耗油量的两倍; 另外, 满意度水平85 %时耗油量与满意度水平80 %时耗油量差异不明显. 所以, 从节能的角度, 建议选用85 %的顾客满意度水平.图8 不同满意度水平下C类顾客点耗油量随顾客规模的变化曲线Fig. 8 Per capita fuel consumption curves of di®erentsatisfaction levels with the number of customers based onclassC表3 R类实例不同满意度水平对人均耗油量的影响(Q= 5)Table 3 In°uence of di®erent satisfaction levels forpercapita fuel consumption based on classR(Q= 5)满意度(%) 60 200 600 800 1 000°= 80 1.01 1.00 1.01 1.00 1.00°= 85 1.00 1.00 1.00 1.00 1.00°= 90 0.99 1.13 1.05 1.07 1.02°= 95 1.16 1.37 1.33 1.36 1.34°= 100 1.83 2.17 2.16 2.32 2.294.5 顾客人数对人均耗油量的影响本实验分别采用比较典型的R类实例和C类实例来说明顾客人数对人均耗油量的影响, 实例规模范围为[60, 1 000], 分别测试了不同满意度下的10组数据. 图9给出了不同车辆容量时R类实例不同顾客人数人均耗油量的变化曲线.图9 不同车辆容量下人均耗油量随R类实例人数变化的曲线(°= 85 %)Fig. 9 Per capita fuel consumption curves of di®erentvehicle capacity with the number of customers based onclassR(°= 85 %)由图9 可以得出, 对于任意车辆容量, 随着顾客人数的增加, 人均耗油量减少; 当车辆容量为4期 杨培颖等: 面向最小碳排放量的接送机场服务的车辆路径与调度 431Q= 15;20时, 结论更显著; 这说明在解决车辆碳排放量的问题上规模效益更为明显.
　　5 结论及展望
　　本文首次从碳排放视角建立了以降低其运营过程中的车辆碳排放总量为目标的非线性0-1混合整数规划模型. 重点从顾客点位置分布、车辆运载能力、顾客满意度水平和顾客人数层面分析了对人均碳排放量的影响, 得到如下结论:1)顾客位置分布类型对人均碳排放量虽有影响, 但并不显著.2)随着车辆容量的增大, 人均耗油量减少, 当容量增加到一定程度, 如容量为15和20时, 碳排放量几乎趋同, 说明车辆容量15为最合适的车型.3)随着满意度的增加, 人均碳排放量也会增加;从节能的角度, 建议选用85 %的顾客满意度水平.4)对于任意车辆容量, 随着顾客人数的增加, 人均碳排放量减少; 当车辆容量为Q= 15、20时, 此结论更显著. 在进一步研究中, 我们将继续研究驾驶员的工作状态与行为习惯等因素对燃油消耗和碳排放的影响.
References1 Lin C K Y. A cooperative strategy for a vehicle routing prob-lem with pickup and delivery time windows. Computers andIndustrial Engineering, 2008, 55(4): 766¡7822 Cornillier F, Laporte G, Boctor F F, Renaud J. The petrolstation replenishment problem with time windows.Comput-ers and Operations Research, 2009, 36(3): 919¡9353 Agarwal R, Ergun O. Ship scheduling and network designfor cargo routing in liner shipping. Transportation Science,2008,42(2): 175¡1964 Doerner K F, Gronalt M, Hartl R F, Kiechle G, Reimann M.Exact and heuristic algorithms for the vehicle routing prob-lem with multiple interdependent time windows. Computersand Operations Research, 2008, 35(9): 3034¡30485 Bredstrom D, Ronnqvist M. Combined vehicle routing andscheduling with temporal precedence and synchronizationconstraints. European Journal of Operational Research,2008,191(1): 19¡316 Tsang K S, Hung W T, Cheung C S. Emissions and fuel con-sumption of a Euro 4 car operating along di®erent routes inHong Kong.Transportation Research, Part D: Transportand Environment, 2011, 16(5): 415¡4227 Ahn K, Rakha H, Trani A, Van Aerde M. Estimating vehi-cle fuel consumption and emissions based on instantaneousspeed and acceleration levels.Journal of Transportation En-gineering, 2002, 128(2): 182¡1908 Yu L, Zhang X A, Qiao F X, Qi Y. Genetic algorithm-basedapproach to develop driving schedules to evaluate green-house gas emissions from light-duty vehicles.TransportationResearch Record, 2010, 2191: 166¡1739 Figliozzi M. Vehicle routing problem for emissions minimiza-tion. Transportation Research Record, 2010, 2197: 1¡710 Bektas T, Laporte G. The pollution-routing problem.Trans-portation Research Part B: Methodological, 2011, 45(8):1232¡125011 Dong G, Tang J F, Lai K K, Kong Y. An exact algorithmfor vehicle routing and scheduling problem of free pickupand delivery service in °ight ticket sales companies basedon set-partitioning model. Journal of Intelligent Manufac-turing, 2011, 22(5): 789¡79912 Tang Jia-Fu, Dong Gang, Pan Zhen-Dong, Kong Yuan.Multi-objective model and algorithm of free pickup cus-tomer and delivery to airport service. Journal of Manage-ment Sciences in China, 2008, 11(6): 35¡42(唐加福, 董纲, 潘震东, 孔媛. 免费接送机场服务的多目标规划模型及算法. 管理科学学报, 2008, 11(6): 35¡42)13 Rakha H A, Ahn K, Moran K, Saeren B, Van den BulckE. Virginia tech comprehensive power-based fuel consump-tion model: model development and testing.TransportationResearch Part D: Transport and Environment, 2011, 16(7):492¡50314 Cappiello A, Srinivasan L, Nam E K, Lue A, Zeid M A. Astatistical model of vehicle emissions and fuel consumption.In: Proceedings of IEEE 5th International Conference onIntelligent Transportation Systems. Singapore, Singapore:IEEE, 2002. 801¡80915 Howey D A, Martinez-Botas R F, Cusson B, Lytton L. Com-parative measurements of the energy consumption of 51 elec-tric, hybrid and internal combustion engine vehicles. Trans-portation Research, Part D: Transport and Environment,2011,16(6): 459¡46416 Barth M, Boriboonsomsin K. Energy and emissions impactsof a freeway-based dynamic eco-driving system.Transporta-tion Research, Part D: Transport and Environment, 2009,14(6): 400¡41017 Fagerholt K. Ship scheduling with soft time windows: anoptimisation based approach.European Journal of Opera-tional Research, 2001, 131(3): 559¡571432 自 动 化 学 报 39卷18 Wen M, Cordeau J F, Laporte G, Larsen J. The dynamicmulti-period vehicle routing problem.Computers and Op-erations Research, 2010, 37(9): 1615¡162319 Kritikos M N, Ioannou G. The balanced cargo vehicle rout-ing problem with time windows. International Journal ofProduction Economics, 2010, 123(1): 42¡5120 The VRP Web [Online], available: http://neo.lcc.uma.es/radi-aeb/WebVRP/, November 5, 201221 Wang H K, Fu L X, Zhou Y, Li H. Modelling of the fuelconsumption for passenger cars regarding driving charac-teristics. Transportation Research, Part D: Transport andEnvironment, 2008, 13(7): 479¡48222 Chang D J, Morlok E K. Vehicle speed pro¯les to minimizework and fuel consumption.Journal of Transportation En-gineering, 2005, 131(3): 173¡182