车辆路径规划问题

车辆路径规划问题（精选九篇）

车辆路径规划问题篇1

车辆路径规划问题 (VehicleRoutingProblems, VRP) 是车辆调度系统的核心;在物流配送、应急处突和军事后勤等领域具有广泛的应用背景VRP是一类典型的NP-hard问题, 很难用数学规划的方法进行求解[1]。传统的VRP对现实交通环境进行了一定的简化, 如假设交通网络中所有节点之间都直接连通, 所有路段的通行能力都一致等, 这虽能降低问题的复杂性, 但不符合实际的交通环境[2]。

有效的求解算法一直是VRP问题研究的热点。近年来, 遗传算法、神经网络等智能算法在求解VRP问题时取得了较好的效果, 但存在计算精度不高、易陷入局部极值等缺陷[3]。混沌优化算法 (ChaosOptimizationAlgorithm, COA) 能够在一定范围内不重复地遍历所有的状态, 具有较好的计算精度和全局寻优能力[4]。本文研究一种网络节点不完全连通, 且路段通行能力存在差异的VRP问题, 分析了问题的数学模型, 提出了一种COA求解算法, 并通过具体的算例, 进行了仿真验证。

1问题描述

本文考虑网络节点不完全连通, 且路段通行能力存在差异的VRP问题, 其过程可描述为:在某个交通子网中, 存在一个配送中心和若干个需求节点, 现需从配送中心出发, 规划一条到达某个需求点的最优路径, 使得时间代价最小化。

我们将网络中的节点依次记为Ni, 节点i和节点j之间的路段记为lij, 其中i, j∈ (0, 1, …N) , N0为配送中心, N为节点总数目, 令当前目标节点为Ng假设条件如下:

(1) 在网络中, 部分节点之间直接连通, 另一部分节点之间并不直接连通或其对应的路段目前处于禁止通行状态。用Xij标记这一状态, 若路段lij连通则将Xij记为1, 否则记Xij为+∞。

(2) 通过智能交通系统ITS和全球定位系统 (GPS) , 可以采集网络中交通状况的详细信息。通过对交通流的评估与预测, 可得到各路段的评价信息[5]。我们将该评估值记为EVij。

其它参数定义如下:

(1) Aαg:到达Ng的第α个可行路径方案;

(2) RT (Aαg) :路径方案Aαg的综合指标评价值;

(3) DSij:路段lij的行程距离;

(4) Yαij:路径方案Aαg是否经过路段lij, 若是则记为1;否则记为0。

则考虑节点连通关系约束和路段通行能力差异的VRP可以描述为:

其中, 若Aαg中存在不能通行的路段lij, 即Xij=∞, 从而RT (Aαg) 取值为+∞, 以满足节点连通关系约束。式 (1) 表明在路网信息已知的情况下, 规划目标是通过减少行程距离和选择通行能力好的路段的方式来减少时间代价;式 (2) 用于确保在具体的一次任务中不重复访问同一个节点。

2求解算法

混沌运动是非线性系统中普遍存在的一种现象, 具有遍历性、随机性和规律性等特点。混沌优化算法是根据其遍历性和规律性的特点, 利用混沌变量在一定的范围内不重复地遍历所有的状态, 搜索目标空间的最优解, 因此具有易跳出局部极值计算精度高等优点。

2.1编码方法

为了将混沌变量空间映射到VRP的解空间, 我们采取基于网络节点的编码方法, 每一个可行方案都是一个长度为N的向量, 所有节点在向量中出现且只出现一次, 编号代表对应的节点, 而其在序列中的顺序代表经过各节点的顺序。其中, 出现在目标节点前的部分为有效的编码部分, 代表访问目标节点前所需经过的节点及其排列顺序;而目标节点后的部分为无效部分, 是为了统一编码的长度和保证搜索的充分性而保留在序列中。若当前目标节点为N8, 某路径方案的编码如图1所示。

解码时可知, 该方案为从N0出发, 依次经过节点N1-N3-N6-N4-N7, 最终到达目标节点N8, 不需要经过节点N2和N5。

2.2程序初始化

在进行混沌搜索之前, 需要存在一个初始状态, 即初始向量A $_{g}^{0}$ 。A $_{g}^{0}$ 的产生方法如下:令A $_{g}^{0}$ 的第1位为0, 其第2到第N位是1到N之间所有自然数的随机排列。可见, 所有节点编号在A $_{g}^{0}$ 中出现且只出现一次, 从而确保了初始向量的合法性。

2.3混沌序列的产生

本文利用Logistic映射来获取混沌序列, 如式 (3) 所示。

λn+1=μλn (1-λn) (3)

式 (3) 中n=1, 2…, NM, n为当前搜索代数, NM最大搜索代数;{λn}为混沌序列, 0≤λn≤1;μ是控制因子, 取μ=4, 使系统处于混沌状态。

2.4混沌搜索算子

为实现在问题的可行解空间内的混沌搜索, 需利用合适的算子完成从混沌运动到可行解搜索的映射, 因此我们设计了“交换算子”和“插入算子”, 其实现方法分别如下:

2.4.1 交换算子

由式 (3) 分别产生混沌序列{λ $_{n}^{1}$ }, {λ $_{n}^{2}$ }, 之后由λ $_{n}^{1}$ 和λ $_{n}^{2}$ 分别产生两个位于区间[2, N]内的自然数J1和J2。其中, J1的产生方法如式 (4) 所示。

J1=int (1+ (N-1) λ $_{n}^{1}$ ) (4)

之后, 通过同样的方法由{λ $_{n}^{2}$ }产生J2。其中, int (x) 表示对元素x向下取整, 若J1≠J2, 则将序列中第J1个位置和第J2个位置所对应的元素实现对换, 其它元素保持不变。

2.4.2 插入算子

与产生J1的方法类似, 产生自然数J3。查找目标节点在原序列中出现的位置, 记为J4, 若J3<J4, 则将目标节点从原序列中删除, 然后将其插入到序列中的第J3个位置。

2.5适应度计算

我们将各路径方案的评价指标RT $_{g}^{a}$ 作为评价函数, 如式 (5) 所示。

Fit (A $_{g}^{α}$ ) =RT (A $_{g}^{α}$ ) (5)

式 (5) 中, Fit (A $_{g}^{α}$ ) 的大小表明路径A $_{g}^{α}$ 的优劣情况, 其值越小, 则表明方案越好。

2.6算法流程

求解VRP问题的COA算法的主要流程如下:

(1) 初始化。设置最大搜索次数NM和算子选择参数β;产生初始可行解A $_{g}^{0}$ , 令A $_{g}^{n}$ =A $_{g}^{b e s t}$ =A $_{g}^{0}$ , 其中A $_{g}^{n}$ 和A $_{g}^{b e s t}$ 分别为当前解和目前最优解。

(2) 混沌序列更新。由式 (3) 分别更新混沌序列{λ $_{n}^{1}$ }, {λ $_{n}^{2}$ }和{λ $_{n}^{3}$ }, 之后分别生成位置序数J1, J2和J3。

(3) 可行解更新。在区间 (0, 1) 之间生成随机数δ, 若δ<β, 则选择交换算子, δ>β, 则选择插入算子;之后按照2.4节所述方法实现相应操作。

(4) 最优解更新。若Fit (A $_{g}^{n}$ ) <Fit (A $_{g}^{b e s t}$ ) , 则Fit (A $_{g}^{b e s t}$ ) =Fit (A $_{g}^{n}$ ) , A $_{g}^{b e s t}$ =A $_{g}^{n}$ , 否则保持Fit (A $_{g}^{b e s t}$ ) 和A $_{g}^{b e s t}$ 不变。

(5) 停止准则。若n<NM, 则n=n+1, 返回Step2, 继续搜索;否则终止, 输出Fit (A $_{g}^{b e s t}$ ) 和A $_{g}^{b e s t}$ 。

3仿真研究

为验证所提COA算法的有效性, 我们在Matlab7.0下编写仿真代码, 对一个包含9个节点的交通子网进行仿真研究。为了直观方便, 利用坐标体系表征各节点所在位置, 并以节点间的几何距离作为各路段的长度。各节点的位置坐标如下:N0 (0, 0) , N1 (10, 5) , N2 (10, -5) , N3 (20, 8) , N4 (20, 0) , N5 (20, -8) , N6 (26, 6) , N7 (26, -6) , N8 (30, 0) 。

假设经过对交通网络的通行能力的评估预测, 已经获取子网中各路段的评估权值EVij, 节点之间的连通关系及各路段的评估权值如图2所示。

参数设置如下:最大搜索代数NM=2 000, 算子选择参数β=0.9。

3.1路径方案分析

我们首先以N8为目标节点, 求解到达目标节点的最优路径, 生成的路径方案如图3所示。

由图3可见, 算法所求的最优路径为N0—N1—N4—N7—N8。对照图2可知, 该方案所选择的路段都是连通的, 即保证了目标节点的可达性;同时, 该方案所需经过的节点较少, 且所选路段的距离较短, 因而能有效地减少时间代价。

为了进一步验证算法的有效性, 我们以N3为目标节点, 求得的路径方案如图4所示。

从行程距离来看, N0—N1—N3是一条距离最短的路径, 但对照图1可知, EV1, 3仅为0.1。图4表明, 算法搜索到的最优路径为N0—N1—N4—N6—N3, 有效绕开了路段l1, 3, 且相比其它方案, 具有较短的整体行程。可见, 算法具有较高的可行性与可靠性。

3.2评价函数值比较

为了验证算法的全局寻优性能, 我们仍以N8为目标节点, 将算法最终输出的路径与几种可行路径的评价函数值进行比较, 其结果如表1所示。

由表3可见, 算法输出的路径方案的评价函数值均小于其它路径方案的评价值, 与较差的路经方案3相比, 其适应度值仅为后者的22.8%, 实现了对行程距离和通行能力的全面优化。可见, 算法具有较强的全局寻优能力, 能够按照优化目标的要求求出有效的路径方案, 实现时间成本的最小化。

4结论

本文研究了一种网络节点之间不完全连通, 且路段之间通行能力存在差异的车辆路径规划问题, 分析了问题的数学模型, 并设计了一种针对该类问题的混沌优化算法, 仿真结果表明, 本文的混沌优化算法是求解VRP的一种非常有效的算法。然而, 在实际的交通环境中, 存在许多的不确定性因素, 路段通行能力也是一个动态变化的过程, 因此动态车辆路径规划问题是下一步我们研究的重点。

参考文献

[1]唐连生, 梁剑.突发事件下的车辆路径问题研究综述.现代物流, 2008;30 (12) :56—60

[2]邹旭东, 郑四发, 等.具有交通限制约束的道路网络最优路径算法.公路交通科技, 2002;19 (4) :82—84

[3]张有华, 张翠军.有时间窗车辆路径问题的混合智能算法.计算机工程与应用, 2008;44 (20) :54—60

[4]Tavazoei M S, Haeri M.Comparison of different one-dimensional maps as chaotic search pattern in chaos optimization algorithms.Ap-plied Mathematics and Computation, 2007;187 (2) :1076—1085

车辆路径规划问题篇2

利用微正则退火算法求解车辆路径问题

在建立单配送中心的车辆路径问题模型后,提出了一种基于微正则退火算法的求解方法,对一个包含20个需求节点的单配送中心实例进行了实验分析.实验数据表明,微正则退火算法能以较大概率搜索到最优路径集,与传统模拟退火算法相比,它的优势是目标函数值下降更快,能够在较短时间内搜索到满意解.

作者：徐俊杰 XU Jun-jie 作者单位：安庆师范学院,经济与管理学院,安徽,安庆,246133 刊名：安庆师范学院学报（自然科学版）英文刊名：JOURNAL OF ANQING TEACHERS COLLEGE(NATURAL SCIENCE) 年，卷(期)： 15(2) 分类号：U491 关键词：交通工程车辆路径问题微正则退火算法全局优化

需求可拆分车辆路径问题研究综述篇3

关键词：需求可拆分车辆路径问题；分支；国内现状

一.引言

传统的VRP一直是网络最优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，多年以来，受到国内外广泛关注。传统的VRP假定每个客户端的需求只能由一辆车来完成，即需求不可以被拆分，但实际应用中，有可能会存在相当一部分任务点的需求量比较大，此时，如果仍然要求每个客户点只能由一辆车来完成服务，势必会造成车辆的空载率提高，浪费运输资源。1989年Dror & Trudeau首次提出了SDVRP的概念[1]，并指出 SDVRP 是一种约束松弛的 VRP，即每个客户点的需求由传统VRP中的只能由一辆车满足，扩展为可以由多辆车满足，这可使得车辆数量和路线总长得到节约。

二.SDVRP的分类

根据研究重点的不同，SDVRP 有多种分类方式。虽然诸如带时间窗、带集货和配送的VRP在传统VRP问题中已经被大量研究，但是，在SDVRP情况下，仍然会得出一些有意义的结论。根据对国内外文献进行归纳，常见的SDVRP的分支主要有以下几类：

（一）带时间窗限制（SDVRPTW）。

带时间窗限制，意味着订单必须在顾客规定的时间段内到达，带时间窗限制的车辆路径问题（VRPTW）屬于传统VRP分支。Archetti et al.提出了第一个求解SDVRPTW的精确算法 [2]。他们运用禁忌搜索算法和新的有效不等式对子问题分别求解，一种新的启发式算法则被用于寻找最优拆分点。实验结果表明，该求解方法对顾客规模为100的SDVRPTW同样具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的启发式算法，是由Ho & Haugland提出的[3]，该算法将SDVRPTW的求解规模扩大至100以上。

（二）带集货和配送限制（SDVRPPD）。

在SDVRPPD中，无时间窗和最大车辆路线限制，但每一节点只能被一辆车访问一次，且每一节点可能同时具有收货和配送两种需求，任一节点的需求都可能超过车辆容量。其目标函数是通过最小化车辆使用数目来最小化总运输成本。这一应用在实际生活中非常常见，如快递员在送货的过程中，经常也会收到客户寄送货物的需求.Nowak et al.通过研究证明[3]，在同一地理分布的顾客群下，当订单平均大小为车载容量一半时，拆分能够获得最大的收益。

（三）利润最大化

一般情况下，SDVRP的目标函数是最小化车辆行驶路线或运输成本，有时也对使用成本进行优化。但是，由于需求可拆分，可能带来额外收益。Brnmo et al.通过数学规划模型并整合分区的方法对此类问题进行求解[3]，结果证明允许拆分可以提高物流企业利润率。

（四）库存和生产

自从供应链管理的观念提出以来，库存路径问题已为很多学者关注。由于库存的概念是基于时间、库存成本以及库存容量之上，时间成为SDVRP中考虑的一个重要因素。在这些问题中，一个顾客通常在特定的时间范围可以被访问多次，但是一个配送日内只能访问一次。同时，库存路径模型还会考虑生产制造策略。

（五）其他

除了以上四种主要的SDVRP分支以外，考虑最小损耗率、混合车辆编队、随机性、需求的离散性以及弧路径的SDVRP分支也逐渐出现在国内外研究中，限于文章篇幅不在此一一赘述。

三.国内研究现状

当前，国内对SDVRP的研究尚不多见。隋露斯，唐加福等用蚁群算法求解SDVRP[4]，给出了基于整数规划的描述方法；通过仿真实验发现，该算法对车辆数目和运输距离的改进显著。鲁强等用遗传算法求解K-SDVRP[5]，数值试验表明，某些条件下，SDVRP较VRP车辆使用数和车辆运输距离更少。孟凡超等通过改进传统的数学模型[6]，建立SDVRP数学模型，利用禁忌搜索算法对SDVRP进行求解。算例结果表明，该模型可以节省车辆数目、缩短路线长度、提高车辆装载率。杨亚璪等等对SDVRPPD进行研究[7]，算例结果表明，所设计的算法可以得到合理的车辆路径，特别当集货需求的总量小于送货需求的总量时，优化效果更好。

无论是使用蚁群算法、禁忌搜索算法还是遗传算法，隋露斯、鲁强、孟凡超以及杨亚璨等人关于可拆分车辆路径问题的研究，都是在需求确定的情况下研究SDVRP，并未考虑客户的时间窗以及需求的随机性。

四.结论

在对SDVRP的主要分支以及常用求解方法进行总结的基础上，我们发现目前对SDVRP的求解方法主要是通过混合整数规划建模并整合精确或者启发式算法对问题进行求解，但随着问题规模的扩大，其求解面临着维数灾难的问题。计算机仿真作为一种新的建模方法，随着计算机技术的发展，使研究者可以通过搜索海量解空间找到问题的次优解或者最优解，为求解SDVRP提供了一种新的解决途径。（作者单位：深圳大学）

参考文献

[1]Dror， M.， Trudeau， P.， 1989. Savings by split delivery routing. Transportation Science 23， 141–145.

[2]Archetti， C.， Bouchard， M.， Desaulniers， G. Enhanced branch-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science.2011.

[3]Archetti C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22

[4]隋露斯，唐加福. 用蚁群算法求解需求可拆分车辆路径问题[C]. 中国控制与决策会议. 2008：997-1001

[5]鲁强，唐加福等. 用遗传算法求解可拆分运输的车辆路径问题[C].第二届中国智能计算大会论文集，洛阳，2008年8月3-7日， pp1-5

[6]孟凡超，陆志强等，需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程. 2010（1）：78-83

车辆路径规划问题篇4

车辆路径问题（VRP）由Dantziq和Ramser于1959年首次提出[1]。它既是物流管理研究中的重要内容，也是运筹学中经典的组合优化问题。VRP是指在满足一定的约束条件下，调用一定的车辆在若干发货点（或收货点）之间进行访问，确定适当的行车路径，以达到设定的目标（如路径最短、费用最低、耗时最短、污染最小等）[2]。

带时间窗车辆路径问题（Vehicle Routing Problem with Time Window,VRPTW）在经典VRP问题的基础上，引入了客户对被服务时间的范围约束，是典型的NP(Nondeterministic Polynomial）问题。用传统的求解方法解决该类问题时，会产生求解速度慢、计算量过大等问题。因此，近年来解决该类问题的焦点集中在启发式算法上，如混合算法求解带时间窗车辆路径（VRPTW）问题[3]，禁忌搜索算法求解VRPTW问题[4,5]，遗传算法求解多目标带时间窗车辆路径（MVRPTW）问题[6]，粒子群算法求解同时取送货的车辆路径问题[7]。

细菌觅食优化算法（BFO)[8,9]是由K.M.Passino于2002年提出的一种元启发搜索算法。其生物学基础是人体肠道内大肠杆菌（E.coli）或粘细菌（M.xanthus）在觅食过程中，一边感应自身周围的化学物质浓度（例如，营养液、有毒物质或菌落中个体间传递的信息素），一边做出远离或趋向该种物质的智能行为，遵循了最优觅食理论[10]。基于细菌智能性提出的算法是一类基于群体的优化技术，具有算法简单、收敛速度快的特点，在优化过程中，无需对象的梯度信息，具有较强的通用性。另外，菌群优化算法易于仿真、实用，国内外学者已经开始关注该类算法。

由于BFO算法提出较晚，目前国内外的研究尚处于起步阶段，研究成果不多，理论也不成熟，因此BFO算法的理论和应用研究都迫切需要开展。迄今为止，关于BFO算法的研究主要集中在以下三个方面：参数的调整、算法的混合和算法的应用。其中，在算法的应用方面，国内外有关细菌行为的优化算法已被成功应用于多个领域：神经网络训练[11]、自适应控制领域[12]、模式识别[13]、车间调度（JSP）问题[14]、投资组合[15]等。在算法应用的众多应用领域中，还多停留在静态、单目标问题的处理上。而针对动态、多目标等复杂优化问题的求解却还不多见。

本文提出全面学习自适应细菌觅食优化算法，并将该算法用于求解带时间窗的车辆路径问题。仿真结果与原始BFO和两种其他改进的BFO算法进行了对比研究，结果显示该算法具有收敛速度快、搜索精度高的特点。

2 细菌觅食优化算法（BFO）的基本原理

细菌觅食优化算法是新兴的随机搜索算法。该算法主要通过趋化操作、复制操作、消除和迁移操作这三种操作迭代来计算函数最优位置，适应度值作为评价细菌个体所在位置的优劣指标。下面介绍这三大操作及其流程[8]。

(1）趋化操作

细菌趋向于营养物质浓度高的区域或者远离有毒物质区域的运动称为趋化。趋化过程靠鞭毛旋转的方向来完成，一次趋化操作由N次游动和翻转组成。鞭毛逆时针转动，细菌以一定的步长（趋化步长）沿着上一步的方向向前游动；鞭毛顺时针转动，细菌以一定的角度在原地翻转。定义θi(j,k,l）表示第i个细菌个体在jth次趋化操作、kth次复制操作及第lth次消除和迁移操作的位置，则更新一次后的位置θi(j+1,k,l）可以表示为：

其中，C(i）为游动一步的趋化步长，Δ（i）为jth次趋化的方向向量。

(2）复制操作

当细菌完成觅食过程中趋化操作之后，按照优胜劣汰的原则，把一些觅食能力弱的细菌淘汰掉，觅食能力强的个体进行复制。细菌i的觅食能力由健康度函数Jihealth来评估：

其中，Nc表示趋化操作的最大步数。将全部S个细菌个体按照健康度函数进行降序排序，保留健康度较好的前Sr=S/2个细菌个体进行自我复制，生成与母体细菌具有相同位置和趋化步长的子体，整个过程保持细菌群体数量不变。

(3）消除和迁移操作

当细菌完成设定的最大复制次数Nre后，或者细菌生存的局部环境发生剧烈变化时（如水的冲刷或温度的突然升高），该部分细菌就会出现迁移到新区域或集体死亡的现象。当细菌个体满足给定的消除迁移概率Ped，该个体就死亡或者随即迁徙到新位置，生成一个具有不同觅食能力的新个体。该操作保持了算法种群的多样性，有利于群体跳出局部最优。

3 全面学习自适应觅食优化算法（ACLBFO）的基本原理

(1）自适应机制

在原始细菌觅食优化算法中，趋化步长C(i）设定为常数[8]。文献[16]提出的BFO-LDC、文献[17]提出的BFO-NDC证明趋化步长C(i）能够平衡算法的全局搜索能力和局部搜索能力，较大的趋化步长能够获得较好的全局搜索能力，较小的趋化步长具有较好的局部搜索能力，合理的设定趋化步长是算法寻优性能优良的关键。为此，本文采用非线性递减调制模型[18]，基于局部版本的自适应趋化步长表达式如下：

其中，n是调制指数，不同的n值产生不同Cmax和Cmin之间的不同趋化步长；a是（0,7]之间的调节系数；Nre为最大复制次数；k为当前复制次数；C(i）为ith次趋化步长。

(2）全面学习机制

在原始BFO中，群体中的细菌个体依靠自身经验搜索食物，与种群中的其它个体没有信息交流。本文将全面学习机制[19]引入原始BFO算法，提出一种全面学习自适应细菌觅食优化算法（Adaptive Comprehensive Learning Bacterial Foraging Optimization,ACLBFO）。

引入学习机制后，每个细菌个体在dth维的位置更新公式如下：

其中，n和m是种群内的随机个体，n∈{1,2，…，S}，m∈{1,2，…，S}，且n≠m；θ和bi是0、1之间的随机数；r1和r2是设定值；λ{1,0}；pc是学习概率，则第ith个细菌的学习概率pc[22]为：

其中，ε为设置的固定参数；rand∈[0,1]。

如果Pc值较大，向pbestid学习的概率就大，向gbestid学习的概率就小。因此，细菌个体不仅能够想自身最好经验学习，也可以向整个种群的最好经验学习。值得注意的是，细菌个体在每一维度都具有全面学习机制。

4 带时间窗车辆路径问题（VRPTW)

(1）带时间窗车辆路径问题模型描述

带时间窗的车辆路径问题可以描述为：在一定的时间约束内，由一个配货中心为一组顾客配送货物，设计车辆的访问路径，以达到设定的目标。

本文考虑的带时间窗车辆路径问题描述如下[20]：假设配货中心有K辆车，每辆车的最大容量用qk(k=1,2，…，K）表示；N个客户要求被服务，各自的需求量用gi(i=1,2，…，N）表示；配送中用N0表示；顾客ith到顾客jth之间的距离用dij表示；每个顾客仅由一辆车服务一次；每个顾客的总需求量≤qk．顾客要求被服务的时间窗为[ETi,LTi]；车辆在顾客i的服务时间为Si，求车辆从配送中心N0出发，经过并服务若干顾客后再回到原配送中心的行车路径，在满足一定约束的条件下，达到设计的目标函数最优。

本文研究的是软时间窗问题，如果车辆到达客户i的时间先于ETi，则需要等待直到到达时间ETi，等待费用用e表示；反之，当车辆到达时间迟于LTi，则迟到费用用f表示。每辆车的速度为vk，车辆到达顾客i的时间为ti，本文假设所有车辆都相同（速度为v，最大载重量为q，单位运输成本为C）。目标函数为运输产生的总费用最小。

该总费用包括车辆在运输中产生的里程费用和车辆早到客户点或晚到客户点所产生的等待或迟到成本。配送过程不考虑环境、交通状况等因素。目标函数描述如下：

该模型中，定义了时间约束，ti为车辆到达顾客i的时间，ETi-ti为车辆在顾客i的等待时间。

(2）全面学习自适应细菌觅食算法求解VRPTW问题

用细菌觅食优化算法求解VRPTW问题，首先考虑的是如何将细菌个体与问题的解一一对应。本文采用二进制编码方式。

假设车辆数为M，有N个顾客需要被服务，采用M+N-1的编码方式。每个细菌个体对应一个M+N-1维向量，第i个细菌的位置表示为xi=(xi,1,xi,2，…，xi,N+M-1）。如细菌群体数设为S，则所有细菌群体的位置表示为X=(x1,x2，…，xS），同时，每种路径产生的费用用f=(f1,f2，…，fS）表示。伪代码如下所示：

(3）仿真实验及结果

本实验用全面学习自适应细菌觅食优化算法求解用4辆车服务8个顾客的问题。实验结果与原始BFO算法和两种改进的BFO算法（BFO-LDC,BFO-NDC）进行比较。参数设置如表1所示。调节指数n和a分别设为2和3，表中的Cstart和Cend分别对应ACLBFO算法中的Cmax和Cmin.

顾客的需求量、装卸货时间和时间窗要求如表2所示。配送中心和顾客之间的距离如表3所示；本实验中，每辆车的承载量为8个单位运输量，速度为50个单位量。表4分别给出了运算10次后4种算法的最大值、最小值、平均值和标准差。从表4可以看出，分别经过10次计算所得的结果中，ACLBFO算法得出的最大值、最小值和平均值与其它3种算法比较都是最好值，说明ACLBFO算法的求解精度更高，规划出的行车路径总费用最低。这是由于全面学习策略的引入，细菌个体在寻优过程中，除了依靠自身的最好经验值外，还能够获得种群中其它细菌个体在各个维度的最好值，引导细菌个体更快速更准确的朝着最优解域前进；表4中的方差值与其它3种算法相比，ACLBFO算法的计算结果也是最小值，说明该算法的稳定性好、鲁棒性强。

最好的顾客服务路径规划是由ACLBFO计算出的结果，如表5所示。辆车1的服务对象为顾客1、6、7，行车路径为从配送中心出发，依次服务顾客1、6、7，最终回到配送中心；辆车2仅服务顾客3，即从配送中心出发，对顾客3进行服务，然后返回配送中心；车辆3的服务对象是顾客4、5、8，行车路径依次为从配送中心到顾客8、5、4，服务完成返回配送中心；车辆4仅为顾客2服务，最后返回配送中心。整个行车路径的费用为975。在4种求解算法中，经典BFO算法计算出的费用最高，其它两种改进BFO算法得出的结果相差不大。

从图1可以看出本文提出的ACLBFO算法在求解过程初期快速收敛，在后期其它3种算法几乎停滞，陷入局部最优时，ACLBFO算法能够跳出局部最优，继续向全局最好值收敛。徒1所示的4种算法的收敛曲线图是对表4所得结论的直观描述。

5 结语

本文将全面学习策略融入到自适应细菌觅食优化算法中，开发了全面学习自适应细菌觅食优化算法（ACLBFO），通过实验对比研究可以得出如下结论：(1)全面学习策略的引入，使得新算法在寻优过程中，细菌个体受到自身最好信息和群体中其它个体历史最好信息的多重指引，增加了细菌个体的多样性、扩大了搜索空间，降低了算法陷入局部最优的风险，提高的算法的搜索精度；(2)自适应的趋化步长递减策略能够更好的平衡算法的全局搜索能力和局部开发能力，促使细菌个体在快速找到最优解域后，细致地开发全局最优解，提高了算法的收敛速度和求解精度。

车辆路径规划问题篇5

城市交通道路的复杂性，固定意识的出行路径引发的严重交通堵塞，使出行者迫切需要获得正确的出行路径;出行过程中，对不熟知地理环境和周围交通状况的把握和了解;车辆及出行者对社会服务的急迫需要;荒野作业过程中的道路迷失。我们可以得出一个重要的结论，就是随着出行者活动范围的不断扩大，人们迫切需要对车辆自身所处的位置及周围环境有更有效的认识，并作出理性的判定[1]。有效调高出行车辆行驶过程中的路径规划效果是解决城市交通堵塞的重要方法。

2 建立静态路径规划数学模型

对于最优道路路径规划策略的研究上来说，道路口节点和路径就可以对智能交通网进行数学逻辑上的描述，这一个基本的数字路网模型图可以表示为：

式中：G为智能交通道路的基本电子路网模型;N为道路网络路口节点的集合，ni为表示道路路网的任意一个节点，xi,yi为该任意节点的横和纵坐标;R为道路路网层路径的ri集合，为道路路网任意一段路径，f为两个道路口节点之间或任意一条道路径的权重值。

依据智能交通原始电子地图，创建交通路网的空间拓扑结构相图G，以此为基础建立静态路径规划数学模型，模型具体描述如下：

2.1 定义智能交通路网的权值变量Q(G)

实际智能交通中的两道路口节点，相关的任意道路径都含有一个权值，依据电路的常用定义规则，称为道路阻抗，描述了车辆行驶过程中通过该道路路径所要消耗的能量变量值，该值可以定义：道路路径的空间距离、通过该道路路径所需时间、车辆行驶路程缴费，依据用户所关心的目标函数可以采用不同的权值测量方法。

最优路径规划的目标函数为：车辆行驶过程中的始末道路最短路径DistanceMin。设Q(G)(28)f{D(R)}，式中D(R)为车辆行驶过程中的路径值，f{D(R)}(28)D(R)。

最优路径规划的目标函数为：车辆行驶过程中的始末道路最短时间DistanceMin。设，式中W(R)为道路路径的宽度和等级，,c为系数。假设车辆的平均速度与道路路径的宽度和等级成正比。

此外，据用户所关心的目标函数可以采用不同的权值测量方法，最优路径规划的目标函数为车辆行驶路程缴费最小的情况时，

注意：列表中的时间0，表示查询时间小于计算机准确定时1ms。需要考虑车辆行驶过程中的道路的收费和油耗，并忽略车辆其他损耗。

2.2 最优路径规划的目标函数T

依据用户所关心的目标函数T，可以采用不同的定义方法。通常在最优路径规划策略考虑，始末道路节点的路径最短、及车辆耗时最小等。

车辆在智能交通网络的行驶过程中，始末道路口节点之间的道路径，分为m条路径，车辆通过每条路径的时间为it。最优路径规划的目标函数T定义为：

标函数T为最小路径：

因为：

则：

3 A-star算法设计

A-star算法是一种路径规划过程中比较经典的预测方式的搜索算法。采用智能交通网的全局信息变量，通过选择合理的预测估计评价函数，预设置优先查询的到路径方向，以减少搜索的道路口节点及路径的路段个数，实现查询的最优效率。以道路口节点之间的欧式距离及道路等级为A-star算法预测启发式的评价指标，定义如下所示：

其中，g(x)是始点到当前节点之间实际所产生的通过道路路径的费用，即是始末两节点之间的，每段路径的道路等级乘以道路的路径长度d(i-,1i)相加的代数和，h'(x)是当前节点到目的地节点的最小代价值，本文取当前节点到目的地节点的欧式距离d(x,t),l(i)为表智能交通道路分类序号值，取值为0、1、2;选择道路等级作为算法价值的评价指标，主要是考虑智能交通网中的高等级路，道路的路况及安全系数较高，虽然不是车辆行驶过程中的最短路径，但是可以给行车者带来精神放松，提升交通安全指标。A-star算法主程序框图如图3.1所示。

4 实验研究

车辆的静态最优路径轨迹规划，以复杂情况较大的北京市东城区的三环和四环之间的道路网数据为路径规划源。东西距离10KM，南北距离4KM。技术平台支持：Inter Pentium 4 1.8GHz,512M内存，Microsoft Windows server 2003操作系统。采用道路网道路功能的两层分类：略图层和详图层，细线为略图层网络结构，粗线为详图层网络结构。交通网略图层包含道路的路径段178条，道路口节点数53个，交通管制的转向限制为8条;详图层包括道路路径段2031条，道路口节点1419个，交通管制的转向限制为2307条。在路径规划仿真平台中，任意选择车辆行驶路径的始末点，A*实验结果统计如表4.1所示。

5 结语

在智能交通网中的静态路径规划算法研究中，具有启发式的A*算法能够实现车辆的静态最优路径规划，最优路径规划策略能够直接有效的提高道路的使用效率。减少城市交通堵塞情况的产生，可以做到节能减排的效果，产生更多的经济和社会效益。

摘要：经济和技术的高速发展,使车辆更加有可能进入普通家庭的生活中,扩展了人类活动的范围和路径,但是也给出行者提出了新的困难和挑战。车辆的静态最优路径规划策略,是利用存储于车载系统的固有静态地图数据,查询始末道路路口节点的最优道路路径算法。静态最优路径规划策略的研究不仅是自主式车载导航信息系统的主要道路路径搜索方法;也是智能交通系统中,基于实时动态路况信息的中心式车辆导航系统的动态路径规划基础。本文应用启发式的路径规划策略A-star(A*)算法,实现了车辆的静态最优路径规划。

关键词：智能交通,A*算法,静态路径规划

参考文献

[1]常青,杨东凯,寇艳红,张其善.车辆导航定位方法及应用[M].北京:机械工业出版社,2005.

[2]陆化普.智能交通运输系统.北京:人民交通出版社,2002.

[3]G.A.Giannopoulos The application of information and communication technologies in transport.European Journal of Operational Research 152(2010):302-320.

[4]王延亮,张玉娟.城市导航电子地图的道路模型.测绘与空间地理信息,2005,28(3):62-64.

车辆路径规划问题篇6

在智能交通道路网中, 一方面当交通实时周围信息不能得到有效的反馈时, 车辆的路径规划只能依据车载交通路网的电子地图进行道路静态路径规划;另一方面, 在能够采集道路交通信息, 并能够对正确的道路交通周围情况进行信息反馈, 可采用车辆的动态最优路径规划, 这也是智能交通工程科研领域研究的热点问题。车辆行驶的动态路径规划比静态路径规划更能够体现车辆行驶过程中状态的可信性、实时性及准确性[1]。

1 单车动态路径规划数学模型

对于最优道路路径规划策略的研究上来说, 道路口节点和路径就可以对智能交通网进行数学逻辑上的描述, 这一个基本的数字路网模型图可以表示为:

式中:G为智能交通道路的基本电子路网模型;N为道路网络路口节点的集合, ni为表示道路路网的任意一个节点, xi, yi为该任意节点的横和纵坐标;R为道路路网层路径的ri集合, 为道路路网任意一段路径, f为两个道路口节点之间或任意一条道路径的权重值。

依据智能交通原始电子地图, 创建交通路网的空间拓扑结构相图G, 以此为基础建立动态路径规划数学模型, 模型具体描述如下:

1.1 模型建立的假设条件:

(1) 忽略交通网交通状况传感器检测的基本误差值; (2) 智能交通网中的动态交通路况信息更新时间T, 符合道路交通信息变化和动态路径规划时间需求; (3) 智能交通网的实时交通信息流, 能实时上传到交通网中心路径规划平台和车载路径规划端。

1.2 建立数学模型

(1) 智能交通路网动态实时信息的R (G, t) 周期时间T内, 认为动态交通信息没有改变。R (G, t) 可采用离散数学方式进行描述, R (G, wi) , 式中wi为周期时间数值为i×T时刻的交通网状态信息。在周期时间T内, 由于当前的交通路况信息不变及道路阻抗不变, 可应用车辆的静态路径规划算法。

(2) 智能交通网中的动态道路阻抗函数确实。假设车辆行驶路段的实时交通平均车流速度, 由安装与城市出租车上的GPS近似估算。取动态道路阻抗为车辆行驶路段的平均动态行驶时间为:

式中dj为道路路径的长度;vij为GPS计算获得的第i个周期T的行驶车辆行驶在j道路路径上的车流量平均速度。

(3) 车辆道路路径规划的价值函数。在车辆的动态最优路径规划中, 不能同静态路径规划的价值函数一致, 即目标函数上不能选取动态交通信息中的最短路径。通常选择车辆行驶的最短路径时间为目标函数, 根据智能交通网的道路交通方式不同, 动态路径规划的价值目标函数即不同。

2 基于周期的单车辆规划算法

该算法的难度系数与车辆行驶工程中, 实时交通信息的更新频率有关。设经过N次交通信息的更新, 计车辆的动态路径规划为N+1。每一次动态道路路径的规划, 应用A*算法, 则算法的难度系数计算累加公式为:

式中b为道路口节点的均值路段数, d为始末节点的查询深度指标。算法的计算量较大, 但是平均分配在车辆行驶过程中的每一个阶段, 则计算量将减少。同时N可以根据具体的时间交通道路信息, 进行必要的调整。基于周期的单车动态路径规划算法流程图如图1所示。

3 实验研究

将智能交通道路的交通状况分为1, 2, 3, 4四个等级, 等级越高, 表示拥挤现象越严重。图中黑色标记的上三角形为车辆行驶过程中的起点, 下三角形为车辆行驶过程中的末点。黑线为车辆的行驶过程中的交通堵塞路径。实验的过程是, 在车辆行驶的路径过程中, 设置交通状态管制信息, 对于实时的当前交通信息, 进行新的路径规划。图2车辆行驶过程中, 改变当前的交通信息, 设置黑线为交通堵塞路径, 重新进行的路径规划, 图3是车辆行驶过程中, 设置的道路拥挤的情况, 新的最优路径规划, 对该交通堵塞道路口节点, 进行了绕行, 最终车辆到达了行驶者设定的末点。

4 结论

基于周期的单车动态路径规划算法, 有效实时的规划车辆行驶道路路径, 可以对交通实时增加的交通堵塞, 进行绕行, 能够降低对车辆行驶者的出行成本, 由于是基于一定周期的自主车辆规划算法, 在基于交通路径规划的中心式处理系统中, 不会出现计算、处理上的不可控, 并能够有利于中心的处理器进行有效的计算。该算法的优势就是在于能够充分使用系统的计算资源。根据申请导航的车辆数量, 进行算法的有效更变频率, 满足了车辆行驶过程中的实时性要求, 同时能够产生相应控制的系统自适应性及鲁棒性。算法的不足之处就是未对车辆行驶过程中, 对交通道路的影响进行考虑。

参考文献

[1]胡金星, 刘允才.面向动态导航的城市路网实时交通信息服务系统研究[J].交通与计算机, 2005 (06) :49-52.

[2]毕军, 付梦印, 周培德.基于城市道路网的快速路径寻优算法[J].计算机工程, 2002, 28 (12) :36-38.

[3]仝秋红, 赵忠杰.汽车驾驶智能化中路线规划及导航的最佳路径求解法[J].西安公路交通大学学报, 1999, 19 (03) :87-90.

[4]A.P.Eiger, P.Mirchandani and H.Soroush, "Path preferences and optimal paths in probabilistic net works, "Transp.Sci, vol.19, no.1, 1985.pp.75-84.

车辆路径问题:研究综述及展望篇7

1 车辆路径问题

车辆路径问题来源于交通运输, 最早是由Dantzig和Ramser[1]于1959年发表在《Management Science》上的文章《The Truck Dispatching Problem》中首次研究了亚特兰大炼油厂向各加油站发送汽油的运输路径优化问题, 并提出了基于线性规划的求解过程。在随后的几十年里, VRP问题得到不断的扩充和发展。

1.1 分类

自车辆路径问题被提出后, Linus (1981) , Bodin和Golden (1981) , Assad (1988) , Desrochers (1990) 等许多学者从不同视角, 按不同标准对该问题进行了分类[2], 例如:按车辆类型分, 可分为单车型问题和多车型问题;按配送中心 (车场) 数目分, 可分为单配送中心 (车场) 问题和多配送中心 (车场) 问题;按任务特征分, 可分为纯送 (取) 货问题和装卸混合问题;按有无时间约束分, 可分为无时间窗问题和有时间窗问题, 另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。

1.2 模型及算法

车辆调度问题是一个较为复杂的组合优化问题, 可以从不同的角度进行建模。一般来说, 车辆调度问题可以构造成整数规划模型, 也可以构造成图论及其他模型, 这些模型之间存在着某种联系, 但从建立模型时的出发点考虑, 大多数模型均可看作是几种模型的变形与组合。

自车辆路径问题提出以来, 国内外学者对于不同类型的车辆调度问题提出了许多不同的数学模型, 并提出了许多获得问题最优解或次优解的算法。车辆路径问题的求解方法, 基本上可分为精确算法、启发式算法和亚启发式算法三大类, 具体分类情况如表1所示。

目前在车辆路径问题模型研究方面, 都是从不同角度、不同方向开展, 例如结合实际考虑时间窗、车场数、车型等要素, 各有侧重。在算法研究中, 国内外都进行了大量的算法研究, 从20世纪60年代的集中在各种形式的节约算法, 到70~80年代提出了各式各样的基于数学规划的算法, 80年代后期时至今日, 各种智能算法和并行算法的广泛应用[4]。由于基本VRP问题属于NP-hard问题, 使得各类VRP问题求解难度更加复杂, 仍值得进一步研究。

从现有研究文献看, 围绕车辆路径问题的研究非常广泛, 在此我们从多车场、多车型、有时间窗VRP问题三方向对现有研究文献进行综述, 并结合社会经济发展所带来的新变化, 对VRP问题未来研究趋势提出看法。

2 多车型车辆路径问题综述

多车型车辆路径问题是车辆路径问题的一种扩展。根据车辆的型号是否相同, 可将车辆路径问题分为单车型问题 (Homogeneous Vehicle Routing Problem, VRP) 和多车型问题 (Heterogeneous Vehicle Routing Problem, HVRP) 。单车型问题假定车辆的型号相同, 即具有相同的最大载重量与最大行驶距离以及相同的固定成本与变动成本, 而多车型问题则不同, 通常各车型的最大载重不同或使用成本不同。

自1984年Golden等首先研究了多车型车辆路径问题以来, 国内外学者针对多车型车辆路径问题的求解算法进行广泛探索。例如:Gendreau等[5] (1999) 用禁忌搜索算法研究了每种车型的数量是无限的HVRP问题, 即FS-MVRP问题。Taillard等[6] (1996) 提出了产生启发式算法求解多车型的车辆路径问题。叶志坚, 叶怀珍等[7] (2005) 总结了国外五种求解多车型问题的启发式算法的优缺点, 并提出了禁忌搜索算法和大旅程法相结合的混合启发式算法。

3 多车场车辆路径问题综述

多车场车辆路径问题 (Multi-Depot Vehicle Routing Problem, MDVRP) 是基本车辆路径问题的扩展, 指的是有数个车场同时对多个用户进行服务, 要求对各车场的车辆和行驶路线进行适当的安排, 在保证满足各用户需求的前提下, 使总的运输成本最低。多车场车辆路径问题, 实际上不仅是路径问题, 它还涉及到了场站的选择和分配问题, 一般可以分解为两个子问题:将顾客分派给场站;为每个场站优化线路。

目前国内外关于多车场车辆调度问题的研究主要集中在算法的改进上, 从传统的启发式算法的应用到现在集中于现代启发式算法的应用, 同时注重结合实际运行情况, 对多车场问题进行扩充。例如:Klots等[8] (1992) 将线性规划和启发式算法结合起来求解MDVRP;Polacek等[9] (2004) 提出一种求解MDVRPTW的变邻域搜索算法;邹彤等[10] (2005) 用遗传算法求解MDVRP问题。此外, 在MDVRP基础上增添时间窗、路况情况、客户优先级等约束条件, 使问题更具研究价值, 例如:陈美军等[11] (2007) 在研究考虑了客户优先级、路况影响、时间窗等多约束情形下的MDVRP问题。

4 带时间窗的车辆路径问题综述

带时间窗的车辆路径问题 (Vehicle Routing Problems with Time Windows, VRPTW) 是基本车辆路径问题的扩展问题, 即在VRP问题的基础上给每个客户加上服务所允许的时间窗约束。时间窗则是一个时间段, 由客户要求的最早服务时间和最晚服务时间确定的一个服务时间区间。这里的时间窗是从客户角度出发, 即可称为客户 (需求) 时间窗。因此考虑VRPTW问题, 不仅需要在空间上进行车辆路径规划, 而且还需要在时间上进行合理的安排。

目前国内外学者对VRPTW问题的研究主要集中在算法研究上。Cordeau等[12] (2001) 提出了求解VRPTW问题通用的禁忌搜索算法;李宁, 邹彤等[13] (2004) 将粒子群算法 (PSO) 应用于带时间窗车辆路径问题 (VRPTW) 中。而且在研究VRPTW问题的过程中, 同时也注重对VRPTW问题的扩充, 例如结合多车场、满载、开放式、车辆租赁等因素, 使研究点更具现实意义。例如:于滨, 靳鹏欢等[14] (2012) 提出一个两阶段的启发式算法来求解MDVRPTW;孙国华 (2012) [15]建立带时间窗的开放式满载车辆路径问题模型, 并设计了改进的自适应遗传算法进行开环路径求解。

5 车辆路径问题研究趋势

随着社会经济的快速发展, 消费者对服务质量要求越来越高, 物流作为生产性服务产业, 作用日益凸显。车辆路径问题作为物流系统优化中的关键一环, 也对之提出更高要求。然而市场竞争的日趋激烈, 使得企业间的竞争更加白热化, 企业与企业间的竞争, 开始转变为联盟与联盟间的竞争, 企业面临更大的压力与挑战。

随着信息技术与互联网技术的突飞猛进, 特别是电子商务的快速发展, 联盟车辆调度问题则会成为车辆路径问题的一个新的应用研究领域。例如:菜鸟网络科技有限公司、重庆市农业电子商务产业发展联盟的成立, 都是通过组建联盟方式, 利用互联网技术, 有效整合资源, 合理调度各个配送企业的车辆资源。

养老服务中配送车辆路径问题研究篇8

养老配送服务主要是物资的调度和人员的指派,涉及到顶点、路网对称性、车场点、车型与车程等元素,这构成了车辆路径问题的元素。但是养老服务的主要对象老人的特点是有时候比较多疑挑剔,喜欢讨价还价,所以对蔬菜和牛奶等的新鲜程度以及某些暂时性短缺的药品的即时性比较高,而此类物品自身对时间的要求也比较严格。同时,老人的出行时间、实际的道路交通状况、车辆行驶速度和配送途中各种意外情况等都是不确定因素,因此,配送过程有时间窗约束。另外,车辆本身对载容量和载重量都有一定的限制。可见,养老服务配送问题实际上就是带时间窗的车辆路径问题。

从车辆路径问题提出至今,国内外学者针对车辆路径问题中配载与配送问题已经有过不少研究。杨锦冬[1]基于客户时间窗约束、道路交通条件约束和车辆承载能力约束等限制条件,建立了车辆总行走时间最短和配载货物最多的两目标优化模型组,反映实际的调度问题。王永亮[2]系统分析了面向城镇连锁经营物流配载与配送组合优化问题的构成要素,研究了多配送中心、多车型、无时间窗限制和软时间窗限制混合、车辆闭环运行的VRP问题。李相勇[3]对车辆路径问题的构成要素和扩展标准作了仔细的讨论和分类,并对各类VRP问题进行了建模和求解。王征[4]对多车场问题作了概述,同时对时间窗问题做了分类,给出了数学模型,并用改进的变邻域搜索算法进行了求解。文章[5]根据城市蔬菜配送公司的实际情况,创新性地同时考虑了车辆路径问题中人力参与较多、多车型、不同车型的固定费用和行驶费用不同且带硬时间窗等问题,并同时考虑车型与任务的相容性。SOLOMO等[6]并未对问题模型进行描述,而是在理论上分析了解决时间窗的车辆路径问题的多种启发式算法。文章[7]则研究了带时间窗的同时收发货的实时车辆路径问题。文献[8-10]则采用了PSO或改进的PSO算法求解。

本文假设要配送的货物是生鲜蔬菜、水果和非处方药品等类型的货物,可以混装,且不考虑多周期配送的问题,将送货地点抽象为社区进行研究。由于客户对生鲜蔬菜和水果的配送优先级的要求有其特殊的时间特征,文中考虑客户的时间窗约束条件和车辆的空间利用率,优化整个配送过程。

1 问题描述与模型

本文将问题描述为简化考虑单配送中心和单车型以及单车程配送的软时间窗问题,且各社区距配送中心的距离以及各社区之间的距离已知。各个社区的货物需求容量已知,每辆车的车型相同,其额定载容量已知,同时已知要求将货物送到的时间窗,要求合理安排车辆的配送路线,使总配送距离最短、车辆利用率最大、超出时间窗的时间总量最少。

为考虑问题的一般性,做如下的模型假设:

1)假定每个社区是一个顾客点,且每个社区点所需的货物不可拆分;2)配送路线对称,且两社区之间的距离即为两地实际地理坐标的几何距离;3)每辆车必须从配送中心发出,最后回到配送中心;4)配送中心的货物总量能满足社区的货物需求量,且各社区的需求量不超过配送车辆的容量;5)忽略卸货时间,且行驶速度始终不变。

建立数学模型如下:

m:配送中心拥有的车辆数

n:顶点数目,n=0表示配送中心,n=1,2,…,n表示各个社区点

dij:各个顶点之间的欧式距离

vi:各个社区的货物需求体积

V:每辆配送车辆的最大载容量(车型相同)

ETi:配送车辆到达第i个社区的最早时间

LTi:配送车辆到达第i个社区的最晚时间

tij:配送车辆从第i个社区到第j个社区的行驶时间,与距离成比例

Si:配送车辆到达第i个社区的实际时间

上述模型中式(1)表示目标函数,是车辆总行驶路程最短、车辆空间利用率最大、早到或晚到时间总量最小四个优化目标的综合,由于四个目标的重要性和量纲不同,赋予不同的权重将多目标变为单目标,其中λ1、λ2、λ3、λ4表示各项权重,根据实际要求进行设置,以此来保证优化目标的层次优先级别[2]。(2)表示每个社区点只能被一辆车服务。(3)表示每个社区点j只能由来之其他点的所有车中的一辆车来服务。(4)表示车辆k的配送路线上的社区点所需求货物的体积之和不超过车辆的额定载容量Q。(5)和(6)分别表示每辆车必须从车场中心发出来服务社区且服务完其路线上最后一个社区后必须回到车场中心。(7)表示车辆实际到达每个社区点的时刻。(8)和(9)分别表示两个决策变量。

实际中老年人更注重时间上的有效性,因而权重系数λ3、λ4应较大,晚到会降低对老人的服务质量,故λ3比λ4要设置的相对小一些。另外,配送中心自身的成本付出中载容利用率和运输距离,更倾向于优化运输距离,故λ1比λ2要设置的大一些,但两者都要小于λ3、λ4。模型中的权重系数可以根据实际问题中对约束条件的要求程度用层次分析法(AHP法)求出[2]。

2 方法描述

2.1 PSO算法的引入

对于车辆路径问题,很多时候并不能找到最优解,而只是找到较优解,因为问题的解即各车辆的排列组合的搜索范围过大。由于问题中约束条件较多,当问题规模较大时,要事先得到一个可行解也十分不容易。而启发式算法中PSO算法则可以很好的解决了这个问题,因为PSO算法实际上是基于迭代的优化启发式算法,系统将为其初始化一个随机解,再经过迭代搜索找到最优解。

PSO的优势十分明显,能对解进行并行处理且鲁棒性好、实现简单、精度高、收敛快,也没有许多参数需要调整,能以较大的概率找到优化问题的全局最优解。但同时它也有一定的缺陷,如在大规模问题中易陷入局部最优[8,9]。文献[10]提出的随机惯性权重PSO算法,能有效克服种群中所有粒子共享同一惯性权重的问题,使所有粒子都能向优化方向移动,从而提高PSO的搜索性能,使搜索过程有效地跳出局部最优,搜索全局最优。

2.2 算法具体过程

1)编码方法

一般文献中对于算法的编码都会采用实数编码方法,即对n个社区点,K辆车服务的车辆路径问题,解的维度D=n+K-1。即在顾客点序列中插入K-1个0,则由0分开的序列组成一个车辆行驶路线。实数编码中维度同时依赖于车辆数和顾客点数目。

文中采用另一种编码方式,让维度只依赖顾客点数目,且更大。对n个社区点,K辆车服务的车辆路径问题,将适应度函数对应的自变量即每个粒子设计为一个2n维的向量,分成2个n维向量:前n维Xk表示顺次客户点所使用的车辆编号,后n维Xo表示各社区在对应的路线中的优先级次序。

这样编码直观的显示出服务每个社区车辆编号,也能明确得出每条路线上车辆服务的先后顺序。同时保证每个社区点都能得到车辆的服务,并限制每个社区点仅能由一辆车来服务,从而减少解的可行性计算过程。另外,PSO算法在多维寻优问题中有较好的特性,维数的增大也不会增加计算的复杂性。

2)更新粒子状态

事先约定种群大小为N,则粒子i(i=,1,2,…),N,在d(d=,1,2,…,2n),维解空间中的速度可表示为vi=(v,i1,vi2,…,vid),位置则表示为xi=(x,i1,xi2,…,xid)。粒子在整个搜索空间内的状态更新将通过下面的两个式子进行更新:

上式中,w表示惯性权重,值越大粒子的全局探索能力越强,值越小粒子的局部挖掘能力越强;c1和c2表示自身和社会的惯性系数,表明粒子自我和群体的学习能力;rand1和rand2是独立的均匀分布于0,,1,之间的随机数。pid是当前粒子搜索到的历史最佳位置,pgd是整个粒子种群搜索到的历史最佳位置。

文献[10]中提出随机惯性权重粒子群算法,其粒子的状态更新公式为:

式中,rand是0~1之间的随机数,。

3)适应度计算

文中数学模型,既有载容量的约束,又有时间窗约束,故采用罚函数来处理,将这些约束条件一起写进目标函数中,而粒子的适应度则直接用目标函数表示。利用PSO算法解决VRP问题的具体流程如图1所示。

3 实验结果和分析

本文设计了一个简单的算例,3辆车服务8个社区,并假定每辆车的额定载容量为V=8。λ1、λ2、λ3、λ4分别取值为0.249,0.037,0.32,0.394。测试如下数据,配送中心和每个社区点的坐标、需求容量数据如表1。

取粒子数N=50,最大迭代数M=100。w=0.7,c1=1.3和c2=2.8,对随机惯性权重PSO算法取参数k=1,随机进行50次计算。得出的最优结果为:车辆1:0-4-0;车辆2:0-3-8-1-0;车辆3:0-2-6-7-5-0。

将三种方式的计算结果进行比较,如表2所示。

将三种方式的PSO算法分别执行50次得到的结果分布情况如图2。

从表2和图2可以得出以下结论:

(1)两种编码的最优值都是143.2,两种编码并没有太多的优劣性,不管采用何种方式,都可以求出最优值,但搜索成功率都不高。

(2)标准PSO算法搜索过程达到最优值的次数小于50%,而采用随机惯性权重PSO进行改进后,只有5次没达到最优值,搜索成功率大大提高。

(3)在相同的执行次数情况下,尽管耗费的时间成本高一些,但随机惯性权重PSO算法达到最优值的次数比标准PSO算法达到的多,所耗费的平均成本也小一些。

综合评估平均搜索时间、平均成本和搜索成功率,随机惯性权重PSO算法对解决VRP问题有较优的效果。

4 结论

本文针对现今社会呈现的老龄化现象,提出了具有代表性的养老服务中的物流配送问题,并建立了合理的数学模型。同时,对PSO算法的编码方式以及标准PSO和改进PSO进行简单的比较,并求解了一个较为简单的算例。结果表明,随机惯性权重PSO算法对于车辆路径问题的求解有较高的搜索成功率。但本文只对养老配送问题中基本的带时间窗VRP模型进行了研究,未考虑速度对车辆行驶时间的影响,也忽略了混装相容性等约束条件对模型的影响,以后可以对这些方面进行更深入的研究。

摘要：文章对社会上老龄化问题涉及到的养老服务工作中的特性化物流配送问题进行了简单分析,建立了相应的带软时间窗的车辆路径问题模型。简明介绍了PSO算法的原理,并利用标准PSO和改进PSO对模型进行了求解和比较,表明PSO算法能较快获得优化结果。

关键词：养老服务,物流配送,时间窗,车辆路径问题,PSO算法

参考文献

[1]杨锦冬,徐立群.城市物流中心车辆配送配载调度指派模型研究[J].同济大学学报,2004,32(11):1452-1456.

[2]王永亮.面向连锁经营的物流配载与配送组合优化模型与算法研究[D].北京:北京交通大学(硕士学位论文),2007.

[3]李相勇.车辆路径问题模型及算法研究[D].上海:上海交通大学(博士学位论文),2007.

[4]王征.多车场带时间窗车辆路径问题的模型和算法[D].大连:大连理工大学(硕士学位论文),2010.

[5]肖和山.城市蔬菜配送车辆调度模型与启发式算法研究[J].湘潮,2009(9):56-58.

[6]Marius M.Solomo.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(2):254-266.

[7]Mei-shiang Chang,Shyang-ruey Chen,Che-fu Hsueh.Real-time Vehicle Routing Problem with Time Windows and Simulta-neous Delivery/pickup Demands[J].Journal of the Eastern Asia Society for Transportation Studies,2003(5):2273-2286.

[8]陈严,刘利民.改进型PSO算法在VRP中的应用[J].计算机工程,2011,37(1):170-172.

[9]黄小燕,文展,等.基于改进PSO的汽车路径优化[J].湘潭大学(自然科学学报),2009,31(2):166-170.

车辆路径规划问题篇9

有容量限制的CVRP可以描述为:一个配送中心有n辆可供运货的车辆, 每辆车有容量 (装载能力) 的限制, 其容量为常数P;有m个配送点, 每个配送点由一辆车服务, 访问且只能被访问一次;每个配送点的需求量di在 (i=1, 2, …, m) 一次服务中全部得到满足。优化的目标为:1) 在满足每个配送点的需求量的前提下使用的车数最少;2) 车辆总的行驶里程最小。

如果将配送中心设为0点, 各配送点的编号为i (i=1, 2, …, m) ;配送点各车辆编号为k (k=1, 2, …, n) ;Cij表示各个节点间的距离, 定义变量xijk, yik, 其中

$\begin{array}{l} x_{i j k} = {\begin{cases} 1, 车辆 k 经过配送点 i 驶向配送点 j, \\ 0, 否则 . \end{cases} \\ y_{i j k} = {\begin{cases} 1, 车辆 k 满足客户 i 的需求量, \\ 0, 否则 . \end{cases} \end{array}$

则其数学模型为[10]

$\begin{array}{l} Μ i n Ζ = \sum_{i = 0}^{m} \sum_{j = 0}^{m} \sum_{k = 1}^{n} c_{i j} x_{i j}; (1) \\ \sum_{i = 1}^{m} d_{i} y_{i k} \leq Ρ ‚ k = 1, 2, \dots, n; (2) \\ \sum_{k = 1}^{n} y_{i k} = {\begin{cases} a, i = 0, \\ 1, i = 1, 2, \dots, m; \end{cases} (3) \\ a \leq n; (4) \\ \sum_{i = 0}^{m} x_{i j k} = y_{i k}; (5) \\ \sum_{j = 0}^{m} x_{i j k} = y_{i k}, \\ j = 1, 2, \dots, m; k = 1, 2 ‚ \dots ‚ n . (6) \end{array}$

上述模型中约束条件:式 (2) 表示每个配送点的用户需求量不大于车辆的总载重量;式 (3) 表示每个配送车辆只能对每个配送点服务一次, 且配送车辆总数为a;式 (4) 表示配送的总车辆数不大于配送中心拥有的总车辆数;式 (5) 、式 (6) 表示服务完成后离开该客户。

2 求解CVRP问题的多种交叉变异策略的混合遗传算法

2.1 染色体编码方式

由于该问题所求目标为如何在使用车辆数最小的情况下使得总运输里程最小。本文针对该问题设计了自然数编码, 在[1, m]中随机产生m个不重复的自然数序列, 组成一条染色体{x1, x2, …, xm}。该染色体只表示对配送点服务的先后顺序, 如何确定车辆数, 本文设计了特殊的解码方式。具体做法是:由于车辆的载重为常数P, 当{P-x1-x2-…-xk≥0、P-x1-x2-…-xk-xk+1<0}时即第一辆车恰好满足配送点{x1, x2, …, xk}的需求量, 该车在完成对配送点xk的服务后回到配送中心, 并计算{0-x1-x2-…-xk-0}的配送走行距离值, 重复该步骤可以确定出染色体{x1, x2, …, xm}需要几辆车进行配送, 并计算出其总走行距离值。这样将问题变为一个目标值, 即确定总走行距离, 并且方便交叉变异操作, 不会产生非法解。实验证明当总走行距离较短时, 车辆数一定也较少。

2.2 选择算子

本文利用基于序评价函数进行轮盘赌选择, 其优点是可以离线计算, 从而节约算法执行时间, 并且选择压力可控。

2.3 多种交叉操作

遗传算法交叉操作是遗传算法中最重要的算子, 也是遗传算法的精髓, 它是决定算法能否产生出更优新解的关键环节, 可以说交叉算子的选择对于算法能否找到最优解起决定作用。

在现行的遗传算法中一种交叉方式贯穿算法始终, 由于在整个算法中对解空间搜索的相似性加之选择算子的作用导致大量父代在进化后期趋于一致, 这又与算法要求种群的多样性产生矛盾, 如PMX交叉在进化后期很难找到新解, 使得算法“早熟”收敛。文献[1]提出一种新交叉NPMX方式, 虽然该算子在一定程度上弱化了对种群多样性的需求, 但是这种算子在进化后期, 种群中仍有大量父代趋于一致, 两个相同的父代经这种交叉后又产生两个相同的子代, 例如:

$\begin{array}{l} A = 8 7 | 4 5 6 1 | 2 3 \\ A 1 = | 4 5 6 1 | 8 7 2 3 \\ \overset{}{\to} \\ B = 8 7 | 4 5 6 1 | 2 3 \\ B 1 = | 4 5 6 1 | 8 7 2 3 \end{array}$

这种交叉方式实际在进行单亲遗传, 但是就产生新解的效率来说不如单亲遗传的方式, 例如同样两个相同的父代:

$\begin{array}{l} A = 8 7 | 4 5 6 1 | 2 3 \\ A 1 = | 4 5 6 1 | 8 7 2 3 \\ \overset{}{\to} \\ B = 8 | 7 4 5 6 1 2 | 3 \\ B 1 = | 7 4 5 6 1 2 | 8 3 \end{array}$

这样会产生两个不同的子代, 扩大了对解空间的搜索范围。但是现行单亲遗传方式也是一种交叉方式贯穿于算法始终, 同样也存在解空间搜索的相似性, 这种相似性在解空间呈“爆炸”状态时, 很难找到全局最优解, 也就是出现早熟收敛的原因之一。为了摆脱这种对于解空间搜索的相似性, 本文引入NPMX交叉和三种单亲交叉方式:PGA1, PGA2, PGA3。在不同阶段进化过程中分别使用三种单亲交叉算子。单亲交叉算子只负责寻找比父代更优的个体, 同时为了使单亲交叉参与到新解空间的探索中, 在循环一定次数后无法找到更优父代个体以一个小概率接受当前产生的个体。现将PGA1、PGA2、PGA3交叉方式说明如下:PGA1算子实际就是NPMX交叉方式进化后期种群中大量父代相同时产生更多新解的单亲交叉方式。PGA2为任意给定一个染色体A随机产生两个交叉点p1, p2 (p1<p2) , 随机产生p3作为p1-p2基因段的移动位置, 当p3∈ (p1, p2]且MAXC-p3+1<p2-p1+1 (MAXC为染色体长度) 即p3的位置应当能放下p1-p2基因段的长度, 将p1-p2基因段放置在p3位置;当p3∈[1, p1) 时移动p1-p2至p3;当p3∈ (p2, MAXC]时p2点与p3对齐, 依次递减放置。具体操作如图1所示。

PGA3采用2-opt领域搜索, 产生新解;引入三个单亲本交叉产生新解, 由于其搜索策略的不同, 避免单一交叉对解空间搜索的相似性。例如表1所示, 说明搜索策略和最优解的结构不同所进行的搜索次数有很大的差异, 利用VC++编程执行20次 (为了比较方便取相同的初始解) 。由该表可以看出初始解相同时, 由于搜索策略和最优解的不同导致搜索次数有很大的差异, 当搜索空间呈“爆炸”式增长时, 所需搜索次数将会有更大的不同, 这样也从另一个角度说明引入不同交叉方式的必要性。

2.4 变异

变异是染色体自发的产生随机变化, 在遗传算法中, 变异可以提供初始种群中不含有的基因, 或者找到选择过程中丢失的基因, 为种群提供新的内容。同时变异算子也是为了遗传算法收敛于更加精确的全局最优解。同样根据交叉分析引入与每种交叉方式对应不同变异算子, 因此, 引入三个变异算子:mutation1, mutation2, mutation3;现对三算子说明如下:mutation1算子为倒位算子。由于PGA1的特点是保留了基因位相邻关系, “倒位变异”就是破坏这种相邻关系搜索到更多的新解。mutation2算子为单点变异即对某一基因点突变, 如图2所示。

mutation3算子为低温退火算子, 在进化后期使用mutation3对个体进行退火操作, 在执行退火时初始温度tk不宜设置太高, 这是因为当温度较低时, SA进行局域搜索, 在进化后期种群中的个体在一定程度上已经逼近全局最优, 局域搜索只是对解进行微调, 考虑到算法效率内层循环数也不宜过大。SA中对新解的产生规则做了如下改进:以较大概率对个体进行“倒位”产生新解, 以较小概率进行2-opt方式产生新解。这样做也是为了避免在退火过程中搜索策略单一和搜索的相似性。降温方法采用降温方程:tk+1=∂tk, ∂=0.95选用零度作业法为终止规则, 即当t小于一个给定的正数ε=0.001时算法终止。同时模拟退火算法在终止时不能保证是本次计算所搜寻到的最优解, 因此加入一个记忆数组s-opt, 每次记录最优解。

3 算法执行步骤

图3为算法流程框架图, 其具体步骤如下:

step1 初始化, 产生初始种群;

step2 如果满足停止条件则输出结果, 计算结束;否则执行以下操作;

step3 计算个体适值, 根据适值排序种群;

step4 如果当前最优解BSF (best_so_far) 适值fit (BSF) 与种群中最佳个体pop[1]的适值fit (pop[1]) 满足fit (BSF) >fit (pop[1]) , 则fit (BSF) =fit (pop[1]) , 无改变代数计数器nl清零, 执行step5;否则直接执行step5;

step5 无改变代数加nl=nl+1;利用轮盘赌选择个体进入新种群;

step6 利用NPMX对种群进行交叉;

step7 判断nl值与进化代数gen的值;

step8 根据step7:如果满足PGA1的执行条件 (本文取nl>=5即5代无改变, gen∈[0, 33]则利用循环执行PGA1 (本文循环10次) , 直到PGA1找到比当前个体更优的解退出循环, 否则以小概率接受当前解 (本文取0.004) ;如果满足PGA2的执行条件, 则执行PGA2 (nl>=10, gen∈[330, 660]) 。否则执行PGA3 (nl>=30, gen∈[660, 1000]) 。继续执行step9;

step9 根据step8执行情况选择变异操作, 如图3所示判断执行;

step10 如果满足则停止计算, 则输出最优解结束;否则转step3。

在step8中对于PGA实际加入了智能交叉[8,9]和以小概率接受当前解的思想, 当某种交叉方式使得无改变次数大于某一值时即出现“早熟”现象, 采用不同交叉策略进行新解空间的搜索, 扩大了解空间的搜索范围。

4 试验及结果分析

本文选取了CVRP问题的4个标准测试数据:A-n32-k5、A-n33-k6、A-n36-k5、A-n39-k6对上述算法与标准遗传算法 (轮盘赌选择、PMX交叉、倒位变异) 进行对比。种群规模取50, 迭代次数1 000, 交叉率取0.95, 变异率取0.004, 退火初始温度取30, 退火速率取0.95, 其他相关参数在算法步骤中已说明, 以下结果均在VC++6.0环境下随机运行20次, 所得最好解如表2所示。

从以上结果可以看出本文在求解上述中等规模的CVRP问题均取得了较好的解, 误差在1.8%以下, 但标准的GA算法求解此类问题误差较大。

为了便于观察本文算法与标准GA算法求解CVRP过程, 本文以求解A-n33-k6的过程为例绘制了, 不同算法当前最优解fit值与进化代数N的关系曲线图 (见图4) 和不同算法随机运行20次所得的结果分布图 (见图5) 。从图4中可以看出标准GA算法在迭代550代左右就收敛了, 再继续迭代也未能找到更好的值。本文算法由于采用了多种交叉策略、变异策略, 在进化前期寻找最优解能力相对较强, 在进化后期由于采用了低温退火策略, 仍然对当前最优解有所改进, 且最终收敛到的解与目前已知最优解的误差较小。图5说明了本文算法相对于标准GA算法, 在20次随机试验中结果比较稳定。

5 结束语

本文对于CVRP问题设计了一种新的混合遗传算法, 算法中加入了多种交叉变异策略, 测试了4个中等规模的国际标准CVRP问题算例, 取得了较满意的解, 并且测试了标准GA算法对于该问题的求解, 测试结果表明本文在求解中等规模的此类问题, 均优于标准GA的算法, 对于今后此类问题的求解可以提供参考。

参考文献

[1]张丽萍, 柴跃廷.车辆路径问题的改进遗传算法[J].系统工程理论与实践, 2002, 8 (8) :79-84.

[2]肖鹏, 李茂军, 张军平, 等.车辆路径问题的单亲遗传算法[J].计算机技术与自动化, 2003, 19 (1) :26-30.

[3]姜昌华, 戴树贵, 胡幼华.求解车辆路径问题的混合遗传算法[J].计算机集成制造系统, 2007, 13 (10) :47-52.

[4]BAKER B, AYECHEW M.A genetic algorithmfor thevehicle routing problem[J].Computers&OperationsResearch, 2003, 30 (5) :787-800.

[5]胡大伟, 朱志强, 胡勇.车辆路径问题的模拟退火算法[J].中国公路学报, 2006, 19 (4) :123-126.

[6]贺国先.现代物流系统仿真[M].北京:中国铁道出版社, 2008:194-275.

[7]汪定伟.智能优化方法[M].北京:高等教育出版社, 2007.

[8]张建彬, 陈抱雪, 隋国荣, 等.智能交叉算子遗传算法的新机制[J].计算机工程与应用, 2009, 45 (32) :35-37.

[9]Hardeberg J Y.Recent Advances in Acquistion and Re-production of Multispectral I mages[C]∥14thEuropeanSignal Proces-sing Conference.Florence, 2006.

本文来自古文书网(www.gwbook.cn)，转载请保留网址和出处

反映能力02-16

反映民生02-16

反映社会02-16

注：本文为网友上传，旨在传播知识，不代表本站观点，与本站立场无关。若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL：66553826@qq.com