电动汽车集散货一体化车辆路径问题

引用本文

邵赛, 毕军. 电动汽车集散货一体化车辆路径问题[J]. 北京交通大学学报, 2017,41(3): 15-21.
SHAO Sai, BI Jun. Electric vehicle routing problem with simultaneously delivery and pick-up[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2017,41(3): 15-21.
Doi:10.11860/j.issn.1673-0291.2017.03.003 复制到剪切板

Permissions

电动汽车集散货一体化车辆路径问题

邵赛, 毕军

北京交通大学交通运输学院,北京 100044

第一作者:邵赛(1989—),女,江西景德镇人,博士生.研究方向为电动汽车、智能交通等.email: shaosai@bjtu.edu.cn.

收稿日期: 2016-09-01

基金: 山东省重点研发计划(2016GGX105004)

摘要

针对电动汽车特性,考虑里程约束和时间窗约束,建立以最小化总费用为目标的电动汽车集散货一体化车辆路径问题模型.模型考虑了车辆可在行驶途中多次前往充电站补充电量.因此,避免由于电量不足导致的车辆半路抛锚及电池过度放电.应用遗传算法求解模型,得到包含配送计划、行车时间及充电计划在内的配送方案.并基于Dijkstra算法求解任意两个邻接节点之间最短路径问题,在路网上为车辆规划行车路线.结合北京市城区路网的算例验证模型和方法的有效性和实用性.

关键词: 电动汽车; 车辆路径问题; 集散货一体化; 充电

中图分类号:U491 文献标志码:A 文章编号:1673-0291(2017)03-0015-07

Electric vehicle routing problem with simultaneously delivery and pick-up

SHAO Sai, BI Jun

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044,China

Fund:Shandong Key R & D Program (2016GGX105004)

Abstract

Based on the characteristics of electric vehicle (EV), this paper, taking the range constraint and time-window constraint into consideration, develops an EV routing problem model with simultaneous delivery and pick-up,aiming to minimize the total cost. To avoid the depletion of battery power and battery over-discharge caused by insufficient battery power, EV powered by on board batteries can recharge at charging stations when travelling. Then, a genetic algorithm (GA) is applied to solve the proposed model, obtaining the distribution solution consisted of distribution plan, timetable and charging plan. Moreover, the shortest path problem between any two adjacent nodes is addressed by Dijkstra algorithm so that the vehicle routes planning can be exerxised in road network. Lastly, a realistic case study on the road network in Beijing urban area is conducted to prove the proposed model and the algorithm effective and practical.

Keyword: electric vehicle; vehicle routing problem; delivery and pick-up; charging

文章图片

作为能够有效减少尾气排放和保护环境的车辆类型, 电动汽车完全符合现代物流业的客观要求, 与近年来所提出的“ 绿色物流” ^[1]发展方向一致.在各种政策补贴和示范运营推广下已应用于物流配送领域.许多相关研究如电动汽车车辆路径问题也引起学者关注.传统的车辆路径问题针对的车辆类型是汽油车.它没有里程限制和充电需求.即使车辆前往汽油站加油, 但加油所花费的时间也很少, 也不会因

此影响整个配送过程.且汽油站分布多, 所以在规划配送方案时不需要考虑分配加油站问题.但电动汽车是全部或部分由电能驱动.其受限的续驶里程使得电动汽车在车辆路径问题中需考虑更多的因素, 如里程约束和充电需求.目前, 针对电动汽车的一般车辆路径问题研究也不多.文献[2]针对电动汽车续驶里程少和充电设施缺乏的情况, 考虑时间窗约束, 提出绿色车辆路径问题, 运用两种启发式算法求解以求到达总的行驶距离最少.文献^[3]研究电动汽车在物流问题“ 最后1 km” 的应用, 考虑顾客时间、货物重量、续驶里程约束, 提出了电动物流车路径优化和调度模型, 避免长时间配送货物的无用路线, 且能在剩余里程不能满足配送任务的情况下选择合适充电站充电.文献^[4]考虑里程约束并允许车辆可在客户点进行充电, 提出充电车辆路径问题, 最后预测平均行驶里程.文献^[5]同时结合充电站选址问题和电动汽车车辆路径问题建立模型.文献^[6]基于电动汽车特征, 重点考虑续驶里程约束、充电需求和充电时间, 建立电动汽车物流配送调度模型, 并用蚁群算法进行求解, 最后分析各配送计划的合理性.文献[7]结合电动汽车的特点, 考虑时间窗问题, 构建了以总配送成本最小为目标的电动汽车车辆路径问题模型.

上述研究针对的物流配送模式为集货型或者散货型, 即从顾客取货送往车场或者从车场载货送往顾客.而对于两种模型相结合的集散型, 在制定配送方案时, 需要考虑货物的双向配送, 常用于快递服务、港口运输等.自20世纪90年代起, 针对该问题的研究^{[8, 9, 10, 11, 12, 13]}越来越受到关注.但较少有结合集散型物流配送模式与电动汽车的研究.

本文作者结合双向配送模型, 着重考虑时间窗约束、里程约束及充电需求, 提出电动汽车集散货一体化车辆路径问题, 合理规划包括配送计划、行车路线、行车时间及充电计划在内的配送方案.

1 问题描述

在传统的集散货一体化车辆路径问题中, 客户要求货物送到的需求时间窗与货物取走的供应时间窗有时候是不一致的, 即每个客户有2个时间窗.针对这个问题, 本文作者将原有的双时间窗问题转化为单时间窗问题进行建模^[14].其具体转化方法是:将每个客户拆分为2个客户, 一个客户表示需求客户, 其需求量为原客户的需求量, 其供应量为0, 其时间窗为原客户的需求时间窗; 另一个客户表示供应客户, 其供应量为原客户的供应量, 其需求量为0, 其时间窗为原客户的供应时间窗; 2个客户的位置均与原客户相同.假设某物流公司需要向L个客户送货和取货, 其中客户i(i=1, 2, …, L)的需求量为q_i, 供应量为u_i, 需求时间窗为[a_i, b_i], 供应时间窗为[a'_i, b'_i]内取走.根据以上条件, 通过拆分客户的方法, 可将上述问题转化为向2L个客户送货或取货的问题.其中客户i(i=1, 2, …, L)的需求量为q_i(即原问题中客户i的需求量), 供应量为0, 时间窗为[a_i, b_i](即原问题中客户i的需求时间窗).客户j(j=L+1, L+2, …, 2L)的供应量为u_j_-_L(即原问题中客户j-L的供应量), 需求量为0, 时间窗为[a'_j_-_L, b'_j_-_L](即原问题中客户j-L的供应时间窗).客户L+1, L+2, …, 2L的位置和客户1, 2, …, L的位置一致.对于考虑时间窗的车辆路径问题, 规划配送车辆的行车时间也是一个重要的决策.本文作者采用“ 早到等待” 的决策原则, 即如果车辆到达客户的时刻早于该客户的时间窗开始时刻, 则让车辆在该客户处等待, 一直等到时间窗开始时刻再进行卸货或装货作业.

由于电动汽车存在电能驱动的特殊性, 充电是电动汽车在行驶过程中面对的问题之一.当电池电量不足以完成整个行程时, 公共充电站为在行驶途中的车辆提供快速便利的充电服务.本文作者采用的充电方式为快充, 其能够在30 min至1 h内快速地完成整个充电过程.充电站可能不会位于既定的行驶线路上, 从而车辆会发生行驶偏移, 增加额外成本.所以, 充电时间和充电成本的增加使得问题更加复杂, 如何为有充电需求的车辆分配最合理的充电站也是本文的研究内容之一.

综上所述, 在传统的集散货一体化车辆路径问题、考虑时间窗的车辆路径问题及充电问题基础上, 电动汽车集散货一体化车辆路径问题可以描述为:依次将客户需要的货物按照规定时间内从车场送到各个客户, 并将客户供应的货物按照规定时间内从各个客户取回车场; 并为充电需求的车辆分配充电站以完成后续行程; 通过合理规划配送方案最小化总费用.由于该问题考虑里程、充电、充电站、时间窗和载重等多个因素, 所以为简化问题, 有如下假设:

1)客户的位置、数量、需求量及供应量已知.每个客户的需求量和供应量均不大于车辆装载容量.

2)客户接受只有两次服务, 即送货和取货.车场派遣车辆为每个客户的送货或者取货要求必须一辆车完成.中途取货的货物与未送完的货物可以混装.

3)车场仅有一个, 位置固定不变.所有车辆从车场出发, 最后返回车场.

4)车辆从起点出发时, 电池为满电状态.车辆可以在途中进行多次充电.充电站离散分布在路网的节点上, 位置和数量已知.

2 模型建立

根据上节的问题描述, 本文作者应用整数混合规划建立电动汽车集散货一体化车辆路径问题模型.模型参数描述如表1所示.其中常量参数的取值依据常识经验和实例数据.

表1 模型参数描述 Tab.1 Model variables description

参数	描述	参数	描述	参数	描述	参数	描述
C₀	总费用, 元	C	C₁∪ C₂	t_ijk	车辆k从点i到点j的行驶时间, min	T'_jk	车辆k到达点j的时刻
$C_{f_{k}}$	车辆固定费用, 元	C₁	取货点集合	D_jk	车辆k到达点 j的剩余里程, km	$T_{jk}^{}$	车辆k离开点 j的时刻
$C_{t_{k}}$	行驶费用, 元	C₂	送货点集合	D_max	车辆最大行驶距离, 120 km	t_c	充电时间, 30 min
$C_{r_{k}}$	充电费用, 元	K	车辆集合	d_ij	点i到点j的行驶距离, km	$T_{0}^{early}$	车辆最早起点出发时间, 6:00
$C_{p_{k}}$	早到或晚到产生的惩罚费用, 元	F	充电站集合	W_jk	车辆k离开点 j的载重量, kg	$T_{0'}^{delay}$	车辆最晚终点返回时间, 21:00
c_f	单位车辆固定费用, 100元/辆	0	起点(车场)	q_j	送货点j的货物重量, kg	z_j	0-1变量.当点j有充电站时, 为1; 否则, 为0
c_t	单位行驶费用, 1元/min	0'	终点(车场)	u_j	取货点j的货物重量, kg	x_ijk	0-1决策变量. 当车辆k从点i行驶到点j, 为1; 否则, 为0
c_c	单位充电费用, 30元/次	s_j	送货点或取货点j的最早到达时间	W_max	车辆装载容量, 1 000 kg	y_jk	当车辆k在点j充电, 为1; 否则, 为0
c_e	单位早到惩罚费用, 1元/min	e_j	送货点或取货点j的最晚到达时间	t_load	卸货或者装货的时间, 10 min	T₀_k	车辆k的行车时间
c_d	单位晚到惩罚费用, 1元/min	V	C∪ F∪ 0∪ 0'

表1 模型参数描述 Tab.1 Model variables description

$Min C_{0} = \sum_{k \in K} C_{f_{k}} + C_{t_{k}} + C_{r_{k}} + C_{p_{k}}$ (1)

$C_{f_{k}} = c_{f} (1 - x_{00'k})$ (2)

$C_{t_{k}} = c_{t} (\sum_{j \in C ⋃ F ⋃ 0'} \sum_{i \in C ⋃ F ⋃ 0'} x_{ijk} t_{ijk})$ (3)

$C r_{k} = c_{c} \sum_{j \in F} y_{jk}$ (4)

$C_{p_{k}} = \sum_{j \in C} (c_{e} \max \{s_{j} - T'_{jk}, 0\} + c_{d} \max \{0, T'_{jk} - e_{j}\})$ (5)

s.t.

$\sum_{\forall i \in C ⋃ F ⋃ 0} x_{ijk} = 1 \forall j \in C$ (6)

$\sum_{\forall i \in C ⋃ F ⋃ 0} x_{ijk} = \sum_{\forall m \in C ⋃ F ⋃ 0'} x_{jmk} \forall j \in C ⋃ F$ (7)

$\sum_{\forall j \in C ⋃ F ⋃ 0'} x_{0 jk} = 1$ (8)

$\sum_{\forall i \in C ⋃ F ⋃ 0} x_{i 0'k} = 1$ (9)

$D_{jk} = [D_{ik} (1 - y_{ik}) + y_{ik} D_{\max} - d_{ij}] x_{ijk} \forall j \in C ⋃ F ⋃ 0', \forall i \in C ⋃ F ⋃ 0$ (10)

$D_{jk} \geq 0 \forall j \in C ⋃ F ⋃ 0'$ (11)

$D_{0 k} = D_{\max}$ (12)

$W_{jk} = (W_{ik} - q_{j}) x_{ijk} \forall j \in C_{1}, \forall i \in C ⋃ F ⋃ 0$ (13)

$W_{jk} = (W_{ik} + u_{j}) x_{ijk} \forall j \in C_{2}, \forall i \in C ⋃ F ⋃ 0$ (14)

$W_{0 k} = \sum_{j \in C_{1}} \sum_{i \in C ⋃ F ⋃ 0} x_{ijk} q_{j}$ (15)

$W_{0'k} = \sum_{j \in C_{2}} \sum_{i \in C ⋃ F ⋃ 0} x_{ijk} u_{j}$ (16)

$W_{jk} \leq W_{\max} \forall j \in V$ (17)

$T'_{jk} = \max [s_{j} - (T_{ik} + t_{ijk}), 0] (1 - y_{jk}) + T_{ik} + t_{ijk} \forall i \in C ⋃ F ⋃ 0, \forall j \in C ⋃ F ⋃ 0'$ (18)

$T_{jk} = [T'_{jk} + (1 - y_{jk}) t_{load} + y_{jk} t_{c}] x_{ijk} \forall i \in C ⋃ F ⋃ 0, \forall j \in C ⋃ F ⋃ 0'$ (19)

$T_{0}^{early} \leq T_{0 k}$ (20)

$T_{0'}^{delay} \geq T_{0'k}$ (21)

$y_{jk} \leq z_{j} \forall j \in V$ (22)

$y_{jk} = \{0, 1\} \forall j \in V$ (23)

$x_{ijk} = \{0, 1\} \forall j \in C ⋃ F ⋃ 0', \forall i \in C ⋃ F ⋃ 0$ (24)

其中:式(6)确保访问每个送货点或者取货点.式(7)表示流量守恒准则, 即车辆达到某节点后需保证离开该点.式(8)和式(9)要求车辆从车场出发, 最后返回车场.式(10)和式(11)考虑里程约束, 即车辆抵达某节点时, 其剩余里程不能小于0.车辆按照由Dijkstra算法^[15]求得的最短路径行驶.式(12)表示车辆从起点出发时, 电池为满电状态.式(13)和式(14)分别表示车辆离开送货点和取货点的载重量.式(15)和式(16)分别表示车辆在起点和终点的载重量.式(17)保证车辆载重量不超过车辆装载容量.式(18)表示车辆到达某节点的时刻.式(19)表示车辆离开某节点的时刻.式(20)和式(21)要求车辆需在车场运营期间完成行程.T₀_k为决策变量之一, 决定车辆行车时间.式(22)确保车辆只能在充电站补充电量.约束条件式(6)~式(24)中有∀ k∈ K.

3 模型求解

车辆路径问题属于NP-hard问题.对于相对简单的网络, 精确算法对车辆路径问题更加适合.而启发式算法在复杂的网络中更能快速地获得较满意解.本文考虑到模型和实验路网的复杂性, 选取遗传算法作为求解方法.对于求解大型网络的车辆路径问题, 遗传算法在求解质量有较好的表现, 并且应用广泛.

在遗传算法中, 通过选择和繁殖产生新的染色体.而适应度更高的染色体能够繁衍到下一代.并应用交叉操作和变异操作取得更好的染色体.染色体编码是如何将决策变量转换为染色体的一个过程, 是遗传算法的第一步骤和基础.本文采用简单直观的序数编码方法.假设有n辆车, m个充电站及L个客户.序数1~L表示取货点, L~2L表示送货点.序数2L+1~2L+m表示充电站.作为起点和终点, 车场在单个路径中需要被访问2次.因此生成2n个虚拟车场(每辆车都会生成一条路径), 由序数2L+m+1至2L+m+2n表示.序数1至2L+m+2n形成一个染色体, 其中每个序数出现有且仅有一次.染色体编码过程如下所示.

Step 1 打乱序数1到2L+m的顺序后, 定义为字符串A;

Step 2 字符串A的首位和末位插入序数2L+m+1和序数2L+m+2;

Step 3 序数2L+m+3到2L+m+2n随机插入字符串A的任意位置.

模型中共有3个决策变量:y_jk, x_ijk和T₀_k.其中, y_jk和x_ijk的解可由染色体解码得到, 而T₀_k则应用穷举法单独求解.本文设置可用行车时间集合, 即在车场运营期间以10 min为一个刻度进行排列如{06:00, 06:10, …, 20:50, 21:00}.每条路径依次从可用行车时间集合中匹配一个行车时间.所有路径的可用行车构成一个行车时间集合, 并结合另外两个决策变量的解计算目标值.最优的目标值所对应的行车时间集合被看作T₀_k的解.模型求解算法实现步骤如下所示.

Step 1 采用染色体编码方法产生初始种群P(g), 其中包含N个染色体.此时g=0.

Step 2 h=0.

Step 3 h=h+1, 并结合y_jk和x_ijk的解对第h个染色体的每个路径应用穷举法搜索最优的行车时间.

Step 4 如果i=N, 转入Step 5; 否则, 转入Step 3.

Step 5 针对每个染色体, 计算目标函数值, 并进行适应度映射后得到染色体适应度.适应度计算公式为

$Z = 1 / C_{0}$ (25)

Step 6 选择N_e个适应度高的染色体作为精英染色体.这些精英染色体不进行交叉和变异操作.剩余的染色体组成普通种群P₁(g)(|P₁(g)|=N-N_e).

Step 7 在种群P₁(g)中的染色体两两成为一组.每组重复执行交叉操作.交叉后要求每个染色体满足所有约束条件.如果不满足, 该组被认定无效, 然后再次执行交叉操作.更新种群P₁(g).

Step 8 在种群P₁(g)中的每个染色体都执行变异操作.变异后要求每个染色体满足所有约束条件.如果不满足, 该组被认定无效, 然后再次执行变异操作.更新种群P₁(g).

Step 9 种群P₁(g)中的染色体和精英染色体组成一个新的种群P(g), 这时g=g+1.

Step 10 如果g小于最大迭代次数, 转到Step 2, 否则, 结束遗传操作, 选取适应度最高的染色体作为最优染色体.

Step 11 对末代种群中的最优染色体进行染色体解码, 求得问题近似最优解, 即配送路线.并输出该染色体对应的最优行车时间.

4 算例及结果分析

4.1 算例数据

选取北京市城区路网(5环内)中的所有快速路和重要主干路去构建算例路网, 共222个节点和943个路段.本文不考虑交通状况对路径的影响, 所有车辆均以匀速行驶(40 km/h).20个充电站(编号S1~S20)和50个客户(编号1~50)随机离散分布在路网节点上, 见图1.其中:圆点、方框和上三角分别表示客户、充电站和配送中心.随机生成客户的需求时间窗、供应时间窗、需求货物重量和供应货物重量, 见表2.

	Figure Option View Download New Window
	图1 路网结构Fig.1 Road network

表2 客户数据 Tab.2 Customer data

4.2 结果与分析

应用遗传算法求解第2节提出的模型, 生成包括配送计划、行车路线、行车时间及充电计划在内的配送方案.考虑到遗传算法的随机性, 本文重复求解模型10次, 选取最优目标值最小的一组实验作进一步分析, 如表3所示.从表3可以看出, 第2组实验为最优, 其具体的配送方案见表4和表5.

表3 实验结果 Tab.3 Experimental results

表4 行车时间和费用 Tab. 4 Timetables and costs

表5 配送计划和充电计划 Tab.5 Distribution plan and charging plan

从表4和表5的结果可得车场需要派出12辆车执行配送任务, 共花费3 527.50元.期间, 由于最大行驶里程(120 km)并不能满足车辆8和车辆10的里程需求, 因此为避免由于电量不足而造成抛锚和电池过度放电等情况, 它们需要在行驶途中分别前往充电站7和2补充电量.每辆车可根据表5依次访问节点完成配送任务或充电任务.车辆行驶路线如图2所示.

	Figure Option View Download New Window
	图2 车辆行驶路线Fig.2 Diving routes

根据最短路径是否充电, 把行车路线分为两种类型:充电行车路线和非充电行车路线.根据行车路线分类, 从10个路径中选取2个路径, 图2为其对应的行车路线.左三角和右三角分别表示取货和送货; 下三角代表同时取货送货; 上三角表示配送中心.

5 结论

1)基于电动汽车技术特点和配送特性, 综合考虑时间窗约束、里程约束及充电需求, 提出最小化总费用的电动汽车集散货一体化车辆路径问题, 并应用整数混合规划建立模型.

2)应用结合穷举法的遗传算法求解模型, 优化包含配送计划、行车时间、行车路线及充电计划在内的配送方案.问题允许车辆在行驶途中多次前往充电站补充电量, 问题模型为有充电需求的车辆规划充电计划.根据Dijkstra算法求解问题模型中涉及到的最短路径问题, 确定配送计划的行车路线.

3)在结合北京市城区路网的实例中, 为完成客户的取货送货需求, 共12辆车被派出.并对具体结果进行了分析, 验证了模型和方法的有效性, 为电动汽车与车辆路径问题相结合的研究提供了理论基础.

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	中华人民共和国国家标准. 物流术语: GB/T 18354—2001[S]. 中国储运, 2001. National Stand ards of P R China. Logistics terms: GB/T 18354—2001[S]. China Storage & Transport, 2001. (in Chinese) [本文引用:1]
[2]	ERDOGAN S, MILLER-HOOKS E. A green vehicle routing problem[J]. Transportation Research Part E Logistics & Transportation Review, 2012, 48: 100-114. [本文引用:1]
[3]	SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520. [本文引用:1]
[4]	CONRAD R G, FIGLIOZZI M A. The recharging vehicle routing problem[C]// Proceedings of the Industrial Engineering Research Conference, 2011. [本文引用:1]
[5]	WORLEY O, KLABJAN D, SWEDA T M. Simultaneous vehicle routing and charging station siting for commercial electric vehicles[C]// IEEE International Electric Vehicle Conference, 2012: 1-3. [本文引用:1]
[6]	刘华旭. 基于电动汽车技术特征的共同配送调度优化研究[D]. 北京: 北京交通大学, 2012. LIU Huaxu. Joint distribution scheduling optimization based on the features of electric vehicle[D]. Beijing: Beijing Jiaotong University, 2012. (in Chinese) [本文引用:1]
[7]	高升. 基于电动汽车的带时间窗的路径优化问题研究[D]. 大连: 大连海事大学, 2015. GAO Sheng. Electric vehicle routing optimization problem with time window[D]. Dalian: Dalian Maritime University, 2015. (in Chinese) [本文引用:1]
[8]	TASAN A S, GEN M. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries[J]. Computers & Industrial Engineering, 2010, 62(3): 755-761. [本文引用:1]
[9]	NAGY G, SALHI S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 162(1): 126-141. [本文引用:1]
[10]	霍佳震, 张磊. 有时间窗的集货送货一体化车辆路径规划启发式算法研究[J]. 物流技术, 2004(5): 64-66. HUO Jiazhen, ZHANG Lei. Study on heuristic algorithm for picking-delivery problem with time window constraint[J]. Logistics Technology, 2004(5): 64-66. (in Chinese) [本文引用:1]
[11]	龙磊, 陈秋双, 华彦宁, 等. 具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J]. 计算机集成制造系统, 2008, 14(3): 548-556. LONG Lei, CHEN Qiushuang, HUA Yanning, et al. Adaptive hybrid genetic algorithm for vehicle routing problem with simultaneous delivery and pick-up[J]. Computer Integrated Manufacturing Systems, 2008, 14(3): 548-556. (in Chinese) [本文引用:1]
[12]	李珍萍, 刘永胜, 王莲花, 等. 双需求集货送货一体化车辆路径问题的数学模型及算法[J]. 运筹与管理, 2009, 18(6): 1-6. LI Zhenping, LIU Yongsheng, WANG Lianhua, et al. Mathematical model and algorithms for double demand vehicle routing problems with backhauls[J]. Operations Research and Management Science, 2009, 18(6): 1-6. (in Chinese) [本文引用:1]
[13]	王晓博, 任春玉. 多车场一体化集货送货车辆路径问题的混合遗传算法[J]. 运筹与管理, 2010, 19(6): 65-72. WANG Xiaobo, REN Chunyu. Study on hybrid genetic algorithm for multi-depot vehicle routing problem with backhauls[J]. Operations Research and Management Science, 2010, 19(6): 65-72. (in Chinese) [本文引用:1]
[14]	郎茂祥. 配送车辆优化调度模型与算法[M]. 北京: 电子工业出版社, 2009. LANG Maoxiang. Vehicle routing problem model and algorithm[M]. Beijing: House of Electronics Industry, 2009. (in Chinese) [本文引用:1]
[15]	DIJKSTRA E W. A note on two problems in connection with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271. [本文引用:1]

2001

0.0

... ^[1]发展方向一致 ...

2012

0.0

... 文献[2]针对电动汽车续驶里程少和充电设施缺乏的情况,考虑时间窗约束,提出绿色车辆路径问题,运用两种启发式算法求解以求到达总的行驶距离最少 ...

2014

0.0

... 文献^[3]研究电动汽车在物流问题#cod#x0201c ...

2011

0.0

... 文献^[4]考虑里程约束并允许车辆可在客户点进行充电,提出充电车辆路径问题,最后预测平均行驶里程 ...

2012

0.0

... 文献^[5]同时结合充电站选址问题和电动汽车车辆路径问题建立模型 ...

2012

0.0

刘华旭. 基于电动汽车技术特征的共同配送调度优化研究[D]. 北京: 北京交通大学, 2012.

LIU

Huaxu

. Joint distribution scheduling optimization based on the features of electric vehicle[D]. Beijing: Beijing Jiaotong University, 2012. (in Chinese)

在现代物流发展的过程中,伴随着城市交通状况、生态环境情况的不容乐观,城市物流的“外部不经济”逐渐引起了人们的重视,在当前经济快速发展的环境下,如何优化城市物流配送方式,协调城市物流活动与城市发展,日益受到社会的广泛关注。本文在此背景下提出设想,如果转变物流运输方式为更高级的共同配送模式,并将作为主要配送工具的烧油汽车改为电动汽车,则能源危机、环境污染等状况将会大大改观。与传统燃油汽车相比,电动汽车可以减少车辆尾气排放、缓解机动车对石油资源的过度依赖,是解决当前能源紧张和环境污染问题的一个重要手段。电动汽车固有的续驶里程(时间)有限和充电时间较长的特点使之与传统汽车的物流配送调度计划有非常大的不同,传统的调度理论与方法不再适合电动汽车车辆的调度,并且由于电动汽车尚处于规模化应用前期,现有考虑电动汽车特点的调度模型与算法的研究尚属薄弱。论文针对上述问题,以对传统汽车的物流配送调度优化问题的研究为基础,重点考虑了共同配送模式下电动汽车有续驶时间和充电时间约束的技术特征,其配送调度的优化问题。建立的第一个模型假设每位客户对于货物到达的时间都有具体要求,并且加之电动汽车的续驶里程约束,即以保证客户对于时间的要求为前提,建立考虑车辆续驶里程的路径优化模型。论文又针对电动汽车的另一个特点——充电需求,进行了全面分析,建立相关模型解决有充电时间约束的车辆调度问题,宏观的考虑一个配送中心各配送计划之间安排的合理性。解法方面,本文分别运用蚁群算法及其改进策略、集合论、图论等方法探讨了模型的求解方法,并通过实例进一步验证了模型的可行性。

... 文献^[6]基于电动汽车特征,重点考虑续驶里程约束、充电需求和充电时间,建立电动汽车物流配送调度模型,并用蚁群算法进行求解,最后分析各配送计划的合理性 ...

2015

0.0

高升. 基于电动汽车的带时间窗的路径优化问题研究[D]. 大连: 大连海事大学, 2015.

GAO

Sheng

. Electric vehicle routing optimization problem with time window[D]. Dalian: Dalian Maritime University, 2015. (in Chinese)

目前我国大中城市普遍面临着空气污染的困扰。我国的城镇化进程一方面引起我国城镇居民汽车保有量快速增加,另一方面导致城市物流配送量猛增。据相关调查,空气中60%-70%CO和40%的NOx来源于汽车尾气。因此,汽车的节能减排将对空气污染问题的解决起到关键作用。如果无污染、高效能的纯电动汽车得到广泛推广,无疑将对城市污染问题的解决大有益处。随着国家关于电动汽车的相关法律法规的完善和扶持政策的推出,电动汽车正在进入千家万户。除此之外,我国物流配送企业也在试验将电动汽车运用于物流配送领域。2013年2月,北京4家单位投入70辆纯电动物流车。2013年7月,全国首台“换电式”纯电动的城市物流配送车辆在郑州正式上路。纯电动汽车和传统汽车相比,具有续驶里程短、充电时间长、充电站少等特点。传统配送车辆的路径优化问题模型不适应于电动汽车,而国内对基于电动汽车的车辆路径问题研究较为匮乏。基于上述原因,本文对基于电动汽车的车辆路径优化问题进行了深入研究,试图解决如何在现有的条件下,通过科学合理的路线规划使得物流配送中心的电动汽车运营达到最佳效果。本文主要做了如下研究：(1)本文首先梳理了国内外对车辆路径优化问题和电动汽车运营管理问题的相关研究,对前人的研究成果加以总结。在前人研究的基础上,本文结合电动汽车的特点构建了以总配送成本最小为目标的带有惩罚函数的基于电动汽车的VRPTW模型。(2)对求解车辆路径优化问题的各种方法进行比较之后,本文采用遗传算法,设计了适合求解本文模型的染色体编码方式和遗传算子。算例分析结果验证了模型及算法的有效性。

... 文献[7]结合电动汽车的特点,考虑时间窗问题,构建了以总配送成本最小为目标的电动汽车车辆路径问题模型 ...

2010

0.0

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2005

0.0

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2004

0.0

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2008

0.0

龙磊, 陈秋双, 华彦宁, 等. 具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J]. 计算机集成制造系统, 2008, 14(3): 548-556.

LONG

Lei

, CHEN

Qiushuang

, HUA

Yanning

, et al. Adaptive hybrid genetic algorithm for vehicle routing problem with simultaneous delivery and pick-up[J]. Computer Integrated Manufacturing Systems, 2008, 14(3): 548-556. (in Chinese)

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2009

0.0

李珍萍, 刘永胜, 王莲花, 等. 双需求集货送货一体化车辆路径问题的数学模型及算法[J]. 运筹与管理, 2009, 18(6): 1-6.

Zhenping

, LIU

Yongsheng

, WANG

Lianhua

, et al. Mathematical model and algorithms for double demand vehicle routing problems with backhauls[J]. Operations Research and Management Science, 2009, 18(6): 1-6. (in Chinese)

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2010

0.0

王晓博, 任春玉. 多车场一体化集货送货车辆路径问题的混合遗传算法[J]. 运筹与管理, 2010, 19(6): 65-72.

WANG

Xiaobo

, REN

Chunyu

. Study on hybrid genetic algorithm for multi-depot vehicle routing problem with backhauls[J]. Operations Research and Management Science, 2010, 19(6): 65-72. (in Chinese)

... 自20世纪90年代起,针对该问题的研究^{[8,9,10,11,12,13]}越来越受到关注 ...

2009

0.0

... 针对这个问题,本文作者将原有的双时间窗问题转化为单时间窗问题进行建模^[14] ...

1959

0.0

... 车辆按照由Dijkstra算法^[15]求得的最短路径行驶 ...