文摘
本研究提出了一种遗传算法解决biobjective有时间窗车辆路径问题同时考虑总距离和距离活动车辆的平衡。一个新的复杂的染色体是用来呈现活跃的车辆路线。通过比赛选择、一点交叉和变异算子迁移,解决问题已经解决了。实验在所罗门的基准问题,考虑到总距离和距离平衡,结果改进在所有类别的问题。根据实验结果,提出的方法是充分的,平均遗传算法性能好。
1。介绍
车辆路径问题(VRP)是最具吸引力的主题之一操作研究,物流和供应链管理。VRP处理物流系统的总成本最小化。vrp是众所周知的组合优化运输物流过程中出现的各种问题,通常涉及调度在受约束的环境。在交通管理中,有一个需要提供服务从供给角度(仓库)各种地理上分散的点(客户)与重大经济影响。由于蚁群的重要的应用,许多研究人员已经开发出解决这些问题的方法。
有时间窗车辆路径问题(VRPTW)是一个变种的VRP和添加时间窗约束模型。VRPTW,能力有限的一组车辆路由从中央仓库与已知一组地理上分散的客户需求和预定义的时间窗口,以便车辆机队规模和总旅行距离最小化,能力和时间窗约束得到满足。由于其固有的复杂性和有用性在现实生活中,VRPTW继续引起研究人员的注意,已经成为网络优化中的一个著名问题,因此许多作者开发了基于精确和启发式方法不同的解决方法。
许多具体的优化方法已经被用来解决VRPTW(这是一个著名的np困难问题1]。一个精确的算法(2和削减技术的分支。因其复杂性,只能解决小规模模型(3)和这些方法效率不高(4]。到目前为止科尔的工作(5)是一种最有效的方法来解决100 -客户规模的实例。因此,许多研究人员调查了VRPTW使用启发式和metaheuristics方法。
近年来,近似方法用于VRPTW代替精确方法考虑到后者的成本高到极点。各种启发式方法可能会发现在文献[6,10]。这些方法,包括模拟退火(7),和禁忌搜索8),提出了在文学。遗传算法VRPTW [6,9- - - - - -11]也许使用最广泛的解决方案,因为它效率。Thangiah [12)提出了一种混合使用遗传算法和局部搜索优化。不同性能的遗传算法、禁忌搜索和模拟退火研究[6,10]。
以上的文献关注的单目标问题VRPTW迄今为止。事实上多目标问题吸引了许多研究者的注意力从这些年来多目标更接近于真实的环境中。一些多重天体vrp制定作为一个函数只使用重量参数确定的显现。Pareto-based方法是好的解决这样的问题,因为经理可以从Paretooptimal输出(自己做决定13]。使用专门的遗传算子和变长染色体表示VRPTW并产生很好的结果在所罗门的56个基准问题[14]。
不同目标分类(15)根据不同的因素,即旅游,资源,和节点活动。巡演,减少行驶距离(或时间)是最常见的目标,同时减少工作负载的不平衡(或差距)研究了车辆在16]。减少汽车的数量是目标相关的资源之一。Ghoseiri和Ghannadpour17]研究了多目标问题,减少车辆的数量和旅行的距离。然而,有时在现实生活中车辆往往受雇于该公司,成本是固定的。这意味着它是不可能降低这种成本通过减少汽车的数量,而总旅行距离是一个重要的经济变量与燃油消耗(18]。此外,车辆的负载平衡是另一个重要的变量,因为管理需求。
本文研究一种biobjective VRPTW考虑同时最小化总旅行距离和工作负载不平衡的车辆。一般情况下,工作负载不平衡包括距离失衡和负载不平衡。然而,在一些真实的生活环境中,也就是说,新鲜食品,好的可以忽略,因为这些订单的重量不重,不影响工作成本。换句话说,本文将考虑多目标的总旅行距离和不平衡的活动车辆的距离。部分2描述了VRPTW问题的配方。部分3论述了遗传算法的过程来解决这个问题。实验和结果分析部分4。最后,部分5为这项工作提供的结论。
2。模型公式
介绍了VRP问题,19),成为最广泛的分析np困难问题。单一目标VRPTW旨在确定哪些客户拜访了每辆车,每辆车的路线服务分配的客户,而乘坐车辆的距离最小化的能力和时间窗约束得到满足。VRPTW已被广泛研究,因为它是最困难的组合优化问题之一,有一个相当大的经济对物流系统的影响11),特别是由于供应链操作的重要性20.]。一些VRPTW问题进行了讨论与具体方法,如拉格朗日理论方法,列生成和动态规划。然而,这些具体方法经常为一些中间和大问题表现不佳。在这种情况下,提出了一些启发式和meta-heuristic方法来解决这些问题。,结果表明,这些方法在可接受的时间获得可行的解决方案。
2.1。配方为VRPTW
非直接完成图可用于模型VRPTW。顶点表示仓库和客户,和边对应于它们之间的链接。
VRPTW可以制定如下。
符号 :是最早的时候给客户吗允许服务。 :是最新的客户允许服务的时候了。 :从节点的成本吗到节点。它被认为是所需的距离或时间从节点到节点。 :是在客户的需求吗。 :是可以使用的最大车辆数。 :是客户的数量加上仓库。仓库是用数字1,客户表示。 :每辆车的装载能力。 :在相应的时间车辆开始服务客户。 :是一个较大的值。 :是决策变量。它等于1如果车辆从节点到节点否则,等于0。
受
方程(1)的目标函数是单目标问题。方程(2)表示,车辆必须旅行从一个节点到另一个。方程(3)表明,变量如果车辆= 1从节点到节点否则,等于0。方程(4)指出,一个客户被一个车只服务一次。通过指定的约束(5),这是考虑到,对于一个给定的车辆的负载不能超过其能力问:方程(6)指定路线的发货仓库。方程(7)保证每个车辆离开和返回到仓库。方程(8)确保观测时间窗口。考虑到一个较大的值,不平等在(9)指定,如果车辆从客户对客户,车辆无法到达客户之前。的变量对应的时间开始服务客户。如果车辆没有服务,不计算。
2.2。随着距离的多目标VRPTW平衡
本文旨在解决硬时间窗的车辆路径问题和路由,进一步研究多目标问题,平衡作为总旅行距离和路线不平衡都最小化。平衡的路线往往是与下列因素有关:(1)平衡每个活跃的访问客户车辆的数量,(2)平衡良好的数量或重量由每个活动车,有时平衡负载率(BLR),表示为(10),车辆的确切负载吗和车辆的能力吗 (3)平衡所需的时间的路线,(4)平衡所需的等待时间的路线,(5)平衡的延迟时间路线,(6)平衡的距离车辆路线乘坐活跃。
在本文中,我们考虑的不平衡路线旅行的距离,它被定义为(11)。和(12)是所有距离的均值。为了更清楚地描述了平衡,我们使用平衡因子代表学位(13)。考虑以下:
3所示。多目标遗传算法
各种启发式和meta-heuristic方法已经提出了解决VRPTW。遗传算法,与其他启发式相比21- - - - - -23),已被广泛用于解决这个问题,因为它的效率和灵活性。三个主要的GA算法运算符,即选择,交叉,变异,可以以不同的方式配置,导致各种GA的组合。Thangiah et al。24首先应用GA VRPTW。在过去的几年中,许多研究已经致力于发展解决VRPTW的气体。遗传算法是一种基于种群遗传学的自适应启发式搜索方法。遗传算法是一个可行的解决方案的解决方案空间利用基因编码的染色体,它定义了一个单独的成员数量。虽然二进制字符串已经在文献中常用的编码染色体,在提出的遗传算法采用整数字符串,每个基因在染色体代表一个客户(或节点)。在单目标遗传算法的问题,特别定义适应度函数通常是但在拖把的应用遗传算法帕累托等级方案经常被使用(25]。帕累托排名过程试图把解决找到nondominated解决方案。因此,根据这个过程每个解决方案给出了等级值的不同的客观值显示解决方案的质量比其它解决方案。很容易融入健身评价过程中的遗传算法代替原始的健身与帕累托排名成绩。这些排名,定义后,分层人口为优先类别。,低等级更可取的,个人在1级是最好的在当前的人口。帕累托排名的想法是保持独立的个人目标。这是通过将当前的候选解决方案视为分层设置或可能的解决方案。每个等级设置的个人代表的解决方案,在某种意义上是无与伦比的。帕累托排名只会区分个人,明显优于其他问题的所有方面。 This contrasts with a pure genetic algorithms attempt to assign a single fitness score to a MOP, perhaps as a weighted sum. Doing so essentially recasts the MOP as a single objective problem. The difficulty with this is that the weighted sum necessitates the introduction of bias into both search performance and quality of solutions obtained. For many MOP’s, finding an effective weighting for the multiple dimensions is difficult and ad hoc and often results in unsatisfactory performance and solutions.
3.1。染色体表示
本文使用一个复杂的由两部分组成的染色体来表示VRPTW的解决方案。染色体是由零号分为两部分由黄色的装饰。的第一部分染色体是一系列整数和每一个整数代表一个客户。我们也称之为customer-part一部分。客户是分开的几个路线,每一个都代表一个序列必须由车辆的交付。的第二部分染色体包含车辆信息。我们也可以调用这部分车部件。车部件数量的基因customer-part等于线路的数量。的数量在每个基因代表其相应的路线的长度。这些数字的总和在车部件必须等于客户的数量。 For example, Figure1显示的表示与8客户和3车辆可能的解决方案。有3个基因在车部件这意味着那些8客户分开3路线。3的第一个基因在车部件代表路线1,服务3客户1、5和4。2第二基因意味着路线2服务2和8。3第三基因意味着路线3服务7、6、3。
这个设计不同于古典方法,路线信息与客户序列混合在一个染色体。存储路径信息和客户单独序列可以表示解决方案更清晰和方便的实现算法,但其对计算效率的影响不是很明显。不失一般性,我们考虑以下的实现三个运营商。
3.2。选择
有几种常用的选择运营商中使用遗传算法选择的过程。轮盘赌选择(RWS)是随机选择从一代创造下一代的基础。遥控武器站使适者个人有更大的机会比弱的生存。这个复制自然健康个体的概率会有一个更好的生存,并将前进形成交配池为下一代。较弱的个体并不是没有机会。本质上这些人可能有遗传编码,为子孙后代可能被证明是有用的。与遥控武器站不同,统一的选择(美国)分配相同的概率对每个染色体的人口。美国随机操作收益和很容易实现。然而,它已被批评为缺乏自然进化与遥控武器站的精神。锦标赛选择(TS)是最常用的操作除了遥控武器站。 The TS operator involves running several “tournaments” among a set of chromosomes chosen at random. The one with the largest fitness is selected for crossover in a pair of chromosomes. The tournament size can be used to adjust the selection pressure. If the tournament size is larger, weaker individuals will have a smaller chance to be selected. This process is repeated until the mating pool is full. Since some experiments indicate that the TS operator outperforms the RWS and US, we choose TS as the selection operator. A possible explanation is that TW always selects the best set of individuals to crossover, whereas RWS and TS are probabilistic and hence some good individuals may be lost in the evolutionary process [26]。
3.3。交叉
一点交叉算子的演变随机选择一个点,一个家长分为两个部分。上述各点的选择以同样的概率。例如,选择交叉点在父母的第三个基因1随机。父的后代继承了左边1和其他基因继承自父类2。另一个孩子是由交换两个父母的角色。图2说明了一点交叉的过程(27]。循环交叉可以产生后代通过一个循环是一个连续的第一的位置的父母。部分映射交叉算子产生的后代通过随机选择两个交叉的点(28]。线性顺序交叉也选择两个交叉点从一个父母和产生新的后代与另一位家长(29日]。一些实验表明一点交叉比另一个更高效的树运营商(26]。因此本文选择单点交叉算子。
3.4。突变
在变异过程中,还有一些变异算子在不同的文献。其中一些是非常复杂的。然而,一些不同的变异算子尝试,他们在GA效率没有显著差异。一个可能的解释,也许突变率总是很小,通常在0.01和0.1之间。采用迁移突变产生的染色体池,避免早期收敛算法。这种突变方法从池中随机选择一个染色体,然后随机选择一个客户从一个路线。然后选中的客户试图插入一个新的路线。如果插入结果产生一个可行的路线,这变异算子成功。否则,重复这个过程直到得到一个可行的解决方案。图3演示了迁移的突变过程。
(一)
(b)
(c)
4所示。实验结果和比较
所罗门的问题由56个数据集,已被广泛用于基准测试不同算法VRPTW文学多年来,因为他们代表相对较好不同的路由场景(14]。这些问题是不同的机队规模、车辆容量、旅游车辆,等等。客户的详细信息包括客户指数的顺序、位置和坐标,对负载的需求,准备时间,到期日期,所需的服务时间。所有的测试问题由100客户,这些客户通常采用VRPTW问题大小的性能比较。客户之间的旅行时间等于相应的欧氏距离。这个问题数据集群分为六类,命名为C1, C2, R1, R2, RC1,分别和RC2。和不同类别显示不同的客户分布和不同时间窗约束。根据客户的位置,问题分类C所有客户集中在组,随机问题类别R所有客户定位,和问题类别RC混合随机和集群的客户。换句话说,客户位于靠近对方的问题类别比R和C客户在RC在中间。这也意味着,R是更加难以得到解决。此外,时间窗口类别1 (C1、R1和RC1)是小于的第二类(C2, R2和RC2)。较小的时间窗口意味着一些候选解决方案更有可能变得不可行的一个小变化后的顺序访问的客户。 Furthermore, for category 1, the time window is also narrow for the depot, which means that only a few customers can be served by one vehicle.
本节描述计算实验进行了调查提出了遗传算法的效率。算法是用JAVA编写的,运行在PC与2.53 GHz CPU和2000 MB内存。标准的所罗门的VRPTW基准问题实例用作实验数据(30.]。经验的计算是基于以下参数:人口规模= 100,一代数量= 500,交叉率= 0.9,变异率= 0.2。
说明不同的模型与路由平衡的影响,我们使用了表的基准问题的最佳解决方案1,2,3数据组C, R,分别和RC。每个表包含了以下内容:在第一列,根据基准问题实例(30.),在第二列,这个问题在文献中,最著名的解决方案在第三列,最好的解决方案发现本文的算法,第四列,通过百分比差异最著名的和最好的发现,在第三列,单目标搜索的平衡率,从去年第二列,最后一列,新的距离值和平衡率biobjective本文的算法。
从表的结果1来3在单目标方法中,发现C1的平衡率,R1和RC1大于C2, R2, RC2平衡时不考虑。换句话说,类别1时间窗较宽有更多空间来改善平衡比第二类与较小的时间窗口。例如,C101的平衡率是42.2%,但在C201是11.2%。
考虑到距离平衡后,biobjective解决方案数据说明改进的平衡率没有影响成本的距离。例如,在C101平衡从42.2%减少到10.3%,距离只减少了约10 (839 - 828.94)。不仅与宽时间窗口的实例得到巨大的改善,但也的狭窄的时间窗口减少平衡利率。
本文的比较数据表明,暗示算法达到更好的路线平衡没有VRPTW解决方案的严重恶化,车队的活跃。从表4最后一列(介绍了平衡改善的程度。
5。结论
本文中讨论的问题具有十分重要的现实意义在员工的劳动平衡的情况下车辆路径的关键动力。在一些情况下,重量不是很重要而活跃的距离车队在考虑劳动力的平衡。
提出了一种遗传算法解决biobjective有时间窗车辆路径问题同时考虑总距离和距离活动车辆的平衡。我们使用了一种新的复杂的染色体呈现活跃的车辆路线。我们选择锦标赛选择、一点交叉和变异算子迁移到解决这个GA。迭代器的操作后,解决了问题的解决方案。实验在所罗门的基准问题,我们发现这目标是接近最著名的文献价值,即使它并不是专为单目标问题。考虑到距离平衡,这些实例不平衡和有很大的提升空间。结果,提高了距离平衡问题的所有类biobjective问题。根据生成的结果,建议的方法是充分的和一般的遗传算法性能是足够的。
确认
作者感谢匿名审稿人的有用的建议和意见。这项工作是由中国国家自然科学基金支持。51105157。