9414数学空间站--打造中国数学学科航母
具有模糊旅行时间的VRP的一种混合遗传算法
作者：佚名 文章来源：本站原创 点击数： 更新时间：2005-12-14具有模糊旅行时间的VRP的一种混合遗传算法
郭耀煌 张建勇
(西南交通大学经济管理学院，四川成都 610031)
摘 要：将传统确定性车辆路径问题扩展为具有模糊特征的模糊车辆路径问题，构建了该问题的数学模型，并通过将模糊逻辑、模糊控制方法与传统车辆路径问题的遗传算法进行有效结合，提出了解决该问题的一种混合遗传算法。最后给出了该问题的一个计算实例。
关键词：模糊车辆路径问题；遗传算法；模糊逻辑；决策者偏好
A Hybrid Genetic Algorithm to the Vehicle Routing Problem with Fuzzy Traveling Time
GUO Yao-huang, ZHANG Jian-yong
（School of Economics and Management，Southwest Jiaotong University，Chengdu 610031，China）
Abstract：The traditional deterministic vehicle routing problem (VRP) is expanded to the situation that the VRP has fuzzy features. The traveling time of the VRP are treated as fuzzy numbers in this paper. After a simple description of the VRP with fuzzy traveling time, a mathematical model for the problem is built. Then, a hybrid genetic algorithm to this kind of vehicle scheduling problem is developed based on the effective combination of the genetic algorithm and fuzzy logistic method. Finally, an example is presented.
Key words：fuzzy vehicle routing problem；genetic algorithm；fuzzy logistic；decisionmaker’s preference
一、引言
车辆路径问题（Vehicle Routing Problem，简称VRP）是指为服务于某类顾客的一个车队，设计一组开始和结束于某中心出发点的最小费用路径。每个顾客只能被服务一次，而且，一个车辆服务的顾客数不能超过它的能力。VRP由于其特有的魅力以及其与运筹学理论研究和实际生产生活的紧密联系，自1959年由Dantzig和Ramser首次提出后，很快就吸引了全世界无数的科学家、工程师和管理学者为之探索，先后涌现出了一大批解决VRP问题的启发式、亚启发式算法，如Clark和Wright提出的节约法[1]，Gillett和Miller提出的Sweep算法 [2]，Lin提出的2-opt和3-opt交换算法[3]等，以及近年来出现的遗传算法（Genetic Algorithm）[4]、模拟退火算法（Simulated Annealing）[5]、禁忌搜索算法（Tabu Search）[6]、神经网络（Neutral Network）算法等等。可以这样说，VRP是运筹学领域这四十多年来研究最活跃、成果最精彩的方向之一。
在以往的绝大多数VRP研究中，人们一般假定在构造路径之前，所有信息（包括顾客信息、车辆信息、路况信息以及线路制定者信息等）都是已知的、确定的，提出的算法也是用来求解确定性条件下的VRP的。但在许多实际应用中，由于受客观世界中不确定性因素以及人类观察、认识事物的模糊性的影响，车辆路径问题的某些参数可能是模糊的、不确定的。在这种情况下，传统确定性条件下的VRP理论和方法不再具有处理这些问题的能力，这就需要研究一整套新的、与传统确定性VRP理论和方法相对应的不确定性VRP理论与方法。本文讨论的模糊车辆路径问题（Fuzzy Vehicle Routing Problem，简称FVRP），就是旨在研究通过对传统VRP理论和方法的拓展，提出一种求解具有模糊特征的车辆路径问题的新算法。
二、问题描述与模型建立
本文研究的模糊车辆路径问题是基于车辆旅行时间的模糊性而提出的，即假定FVRP中只有旅行时间是模糊的，而其它有关VRP参数都是已知的、确定的。此类FVRP可描述如下：某一运输网络中有一车场和m个待服务的节点（顾客），分别以0和1，2，…，m表示，车辆从车场出发，服务一定数量的节点后返回车场，已知每辆车运输能力为C，每个节点需求量为di，车辆在节点i与节点j之间的预计旅行时间为一模糊数
为方便起见，本文设任意两节点i，j间的旅行时间
为构造数学模型，定义变量如下：
总费用最小的具有模糊旅行时间的车辆调度问题的数学模型可构造如下：
(3) (2) (1) (5) (6) (7) (8)
(4)
三、基于模糊逻辑的混合遗传算法
3.1 解决问题的基本思路
对于任意给定的一个车辆路径计划i0，i1，…，ik，（k≤m），由于各节点间旅行时间的模糊性，该车辆路径计划的总计划旅行时间也必然为一模糊数。由模糊数学知识可知，该车辆路径计划的总模糊旅行时间为：
很明显，决策者对任一路径的偏好程度依赖于该路径计划的总旅行时间
图1 决策者偏好程度的模糊集表述 图2 旅行时间的模糊集表述 t1 t2 t3 短 中等 长 旅行时间 低 中 高 p μ μ 0 1
语言表述的偏好程度“低偏好”、“中等偏好”、“高偏好”可以用相应的模糊数集表示，如图1所示。
同样，对任一车辆路径计划，其计划旅行时间也可主观估计为“短”、“中等”、“长”等多种情况，可分别用模糊集S、M和L表示，其隶属函数如图2所示。其中t1和t3可以由决策者根据经验主观给出，也可以像随后的2.3节中那样计算得出。
3.2 基于模糊逻辑的选优
对于任意给定的某个路径计划，很明显，从成本节约的角度出发，该路径计划预计旅行时间越长，决策者选择该路径的偏好程度越低；反之，预计旅行时间越短，决策者选择该路径的偏好程度越高。因此，可将车辆路径规划的模糊逻辑规则归纳如下：
规则1：如果PT(计划旅行时间)=L，那么P(决策者偏好)=Low；
规则2：如果PT=M，那么P=Medium；
规则3：如果PT=S，那么P=High。
这是一个并列的模糊条件语句。根据模糊数学知识，上述每一模糊条件语句都对应一个模糊关系，例如：
如果PT=M，那么P=Medium，其模糊关系可定义为
这里
同理，规则1和规则3分别有如下模糊关系：
整个系统的总控制规则所对应的模糊关系R是各个模糊关系的并集，即
长 低 p μ μ 中 中 p μ μ 短 高 p μ μ p* p μ 图3 决策者偏好值的确定过程
PT
PT
PT
确定过程如图3所示。而要具体确定决策者对某一路径的偏好程度，则必须给出一个确切的值，即须对得出的模糊数进行清晰化处理。最大隶属度方法和重心法通常被用来对模糊数进行清晰化处理，本文采用重心法，则决策者偏好值p*为：
3.3 基于模糊逻辑的混合遗传算法
本文采用自然数编码构造如下的求解FVRP的混合遗传算法。
(1) 构造染色体，产生初始可行种群
初始可行种群可按如下步骤产生：
step1：产生随机顾客排列；
step2：取出顾客排列中最左边的顾客，根据该顾客的需求量和当前车辆的剩余运输能力，确定当前车辆是否