![](https://csdnimg.cn/release/download_crawler_static/19276272/bg1.jpg)
求解
CARP-RP-ML
问题的改进算法
胡
珊,林
丹
(天津大学数学系,天津 300072)
摘 要:传统方法无法有效求解交通道路维护运作中的有补给点及多装载的容量约束弧路径(CARP-RP-ML)问题。为此,提出改进的启发
式算法和遗传算法。启发式算法将不同的分割算法用于由所有需求弧随机排序得到的个体上,构造问题的可行解;遗传算法利用分割算法
计算其个体适应值,确定对应的可行车辆路径及补给位臵,并用局部搜索作为变异算子,进一步扩大搜索空间。数值实验结果表明,与启
发式算法相比,遗传算法能更有效地求解 CARP-RP-ML 问题。
关键词:容量约束弧路径问题;组合优化;启发式算法;遗传算法;适应值;局部搜索
Algorithms for Solving CARP-RP-ML Problem
HU Shan, LIN Dan
(Department of Mathematics, Tianjin University, Tianjin 300072, China)
【Abstract】Capacitated Arc Routing Problem with Refill Points and Multiple Loads(CARP-RP-ML), stems from road network maintenance, is the
CARP with refill vehicles which can refill several times because of multiple loads. A heuristic and genetic algorithm is proposed to solve
CARP-RP-ML. The Heuristic Algorithm(HA) adapts a split algorithm, designed based on two types of vehicle, on each random permutated
individual to construct the feasible solution of the problem. The Genetic Algorithm(GA) uses the split algorithm described in heuristic algorithm to
calculate the fitness of individuals and to determine feasible vehicle routes and replenishment locations, and adopts local search as the mutation to
expand search space. Experimental results show that GA outperforms HA, which demonstrates that GA can more efficiently solve CARP-RP-ML.
【Key words】Capacitated Arc Routing Problem(CARP); combinated optimization; Heuristic Algorithm(HA); Genetic Algorithm(GA); fitness
value; local search
DOI: 10.3969/j.issn.1000-3428.2012.07.055
计 算 机 工 程
Computer Engineering
文章编号:1000—3428(2012)07—0168—03
1
概述
容量约束弧路径问题
(Capacitated Arc Routing Problem,
CARP)
是一个
NP
难问题
[1]
,可描述如下:一个车队从车场出
发,对已知需求的若干个位于弧上的客户进行服务,求在满
足车辆容量约束及其他各种约束条件下的车辆行驶路线,使
服务总成本最小。
目前,国内外关于
CARP
的研究主要集中在该问题的各
种推广及对应的求解方法上。已有的
CARP
推广分为
7
类
[2]
,
如多车场
CARP
、可移动车厂
CARP
。相关求解方法主要分
为精确求解法
[3]
、下界法
[4]
、启发式算法
(Heuristic Algorithm,
HA)
[5]
。
文献
[6]
提出了
CARP
问题的一种新的推广,称之为有补
给点的容量约束弧路径问题
(Capacitated Arc Routing Problem
with Refill Points, CARP-RP)
。该问题来源于对城市交通网络
的路面交通标志进行油漆刷新的实际运作。其中一辆服务车
(Service Vehicle, SV)
进 行油漆操作 , 另 一 辆 补 给 车
(Refill
Vehicle, RV)
为服务车提供油漆补给,限定补给车为多装载,
使得在整个过程中可以为服务车提供多次油漆补给,即得到
有补给点及多装载的容量约束弧路径问题
(Capacitated Arc
Routing Problem with Refill Points and Multiple Loads,
CARP-RP-ML)
。因此,
CARP-RP-ML
可视为车场可移动的
CARP
问题。
该
NP
难问题用传统方法无法有效求解,因此,本文提
出求解
CARP-RP-ML
问题的启发式算法和遗传算法
(Genetic
Algorithm, GA)
。
2 CARP-RP-ML
问题描述
CARP-RP-ML
可用如下图论模型描述:给定连通有向图
,其中,
1 2 | |
{ , , , }
N
N n n n
代表顶点集;
n
1
=n
depot
表示车场;
{ | ( , ), , 1,2, , }
i i j k
A n n j k i m
代表顶点间
的有向弧集,
中
条
要求被服务的弧
(
需求弧
)
组成
集合
,对于任意弧
,都有
。问题涉及
2
种不
同车型:服务车和补给车。任意弧
有非负
SV
行驶费用
和
RV
行驶费用
。问题目标为在满足各约束条件下
使得车辆总行驶费用最小,并同时决定起止于两连续补给点
的两车辆的最短行驶路径。各约束条件如下:每条
SV
路径
上需求总量不超过
SV
的最大容量
;
2
类车均需从车场出
发,最终回到车场;每条需求弧都恰好被一辆
SV
服务一次,
但允许多次经过。
3
基于分割的启发式算法
HA
基于直观或经验而得到,能对优化问题的实例在可
接受的计算成本内给出一个近似最优解,因其简单易行、速
度快等优点而被广泛应用。本文基于分割思想提出的启发式
算法基本步骤如下:生成个体,该个体为由所有
条需求弧
随机排列得到的序列;将所得个体运用分割算法得出对应的
基金项目:教育部留学回国人员基金资助项目
作者简介:胡 珊(1987-),女,硕士研究生,主研方向:进化算法,
运筹学;林 丹,教授
收稿日期:2011-05-16 E-mail:dlin@tju.edu.cn