需求可离散拆分车辆路径问题及其禁忌搜索算法
发布时间：2022-01-05 18:47
针对客户需求常以若干离散订单（批次）构成的问题特性,本文给出需求可离散拆分车辆路径问题的描述及数学模型。对比需求可连续拆分的问题类型,对该问题性质进行了研究,分析提出问题解的特性。本文提出求解该问题的禁忌搜索算法,针对同客户的不同订单（批次）需求,设计两种特殊操作以避免不必要的路径成本,加快搜索速度并增强算法搜索性能。计算结果与现有方法结果进行了比较,表明所提出的算法可以找到更好的解决方案。
【文章来源】：哈尔滨工程大学学报. 2019,40(03)北大核心EICSCD
【文章页数】：9 页
【部分图文】：
SDVＲP最优路径方案
枨罂杀涣???分，可根据车辆剩余装载情况机动地对客户需求以任意方式(需求大小)进行拆分。如图1所示，共有3个客户点(括号内数字为需求量)，各弧旁数字为相邻点间距离。假设车辆装载能力为10，则所需最小车辆数为2。在相应的DSDVＲP中，如图2所示，各客户点的总需求量和车辆装载能力与图1中的例子相同，但各客户需求均由2批(订单)组成(括号内为订单需求量)。采用动态规划算法可分别求得SDVＲP及DSDVＲP在使用最小车辆数且不超载的条件下的最优路径方案。图1SDVＲP最优路径方案Fig．1OptimalsolutiontotheSDVＲP图2DSDVＲP最优路径方案Fig．2OptimalsolutiontotheDSDVＲPDSDVＲP的上述路径方案中，各路径中各包含有3个拆分点，2条路径中公共点个数为3，大于路径数2，总路径长度为10.83，长于SDVＲP总路径长度(9.48)。路径10－1(3)－2(7)－0路径20－1(2)－3(8)－0路径10－1(1)－2(2)－3(7)－0路径20－1(4)－2(5)－3(1)－0对比SDVＲP，DSDVＲP及其最优解具有以下特性(cij、di和Q及其相关限制条件均相同的情况下):1)若Ｒ和Ｒ'分别为SDVＲP和DSDVＲP最优解中任意2条路径间存在的公共点数，存在Ｒ≤Ｒ'，即DSDVＲP最优解中任意两条路径间可能存在多个公共点;2)若L和L'分别为SDVＲP和DSDVＲP最优解中需求拆分点个数，存在L≤L'，即DSDVＲP最优解中拆分点个数可能多于路径数;3)若Z和Z'分别为SDVＲP和DSDVＲP的最优解对应的目标函数值，存在Z≤Z'，即DSDVＲP最优解可能劣于SDVＲP最优解;4)已知SDVＲP为NP－难问题［1，14］，SDVＲP是DSDVＲP的特殊形式，所以DSDVＲP同为NP-Hard问题。2禁忌搜索算法设计2.1解的表达方式本文在算法设计及求解过程的描述中，将各客户的离散需求看成相互独立?
哈尔滨工程大学学报第40卷新路径起点，继续构造新路径。以此类推，直至所有节点均被分配至指定路径为止。2.3同客户节点合并操作由于路径构造时将所有离散的客户订单视为独立节点，故生成的路径中存在同客户订单被分散访问的情况。如图3所示，节点i、j分别表示同客户的不同订单，路径中该客户点被先后访问了2次，增大了不必要的路径成本。为此本文设计同客户订单合并操作，对路径内相同客户的订单进行合并，避免不必要的路径成本，该操作为离散需求拆分的基本路径优化操作，为订单组合的操作奠定基矗图3同客户节点合并操作Fig．3Combinationofitemsfromthesamecustomers2.4同客户节点随机绑定操作一般邻域操作中使用的操作对象为单一的客户节点，因DSDVＲP中的实际个体为各客户订单节点，若简单将客户节点(该客户的全部订单)作为操作对象，则无法体现需求可拆分特性。但若将订单节点作为操作对象，因订单数量远大于客户数，将耗费大量的计算时间。故本文提出一种折中方式，设计同客户节点随机绑定操作，用于邻域操作中实际操作对象的生成及选择。具体操作方式为:在当前解中随机挑选可行的操作对象(节点)，向前向后判断是否存在同客户节点。随后在同客户节点间随机选择若干个连续订单进行绑定，作为接下来邻域操作的实际操作对象。如图4所示，挑选出的操作节点为i，经判断路径中t、i、j、k属于同一客户，t和k分别为起始同客户节点。i、j、k为随机挑选出的连续同客户订单节点，则在下一步邻域操作中将i、j、k绑定视为一个绑定节点i*进行操作。由此可知，经该操作确定的操作对象可能是单一订单节点，如图5;可能是部分订单，如图4和6;也可能是客户点(该客户的全部订单)，如图7，由此增大了操作对象的随机多样性。在?
【参考文献】：
期刊论文
[1]求解需求可拆分车辆路径问题的人工蜂群算法[J]. 姜婷. 四川理工学院学报(自然科学版). 2017(03)
[2]带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 符卓,刘文,邱萌. 中国管理科学. 2017(05)
[3]求解需求可拆分车辆路径问题的聚类算法[J]. 向婷,潘大志. 计算机应用. 2016(11)
本文编号：3570882
【文章来源】：哈尔滨工程大学学报. 2019,40(03)北大核心EICSCD
【文章页数】：9 页
【部分图文】：
SDVＲP最优路径方案
枨罂杀涣???分，可根据车辆剩余装载情况机动地对客户需求以任意方式(需求大小)进行拆分。如图1所示，共有3个客户点(括号内数字为需求量)，各弧旁数字为相邻点间距离。假设车辆装载能力为10，则所需最小车辆数为2。在相应的DSDVＲP中，如图2所示，各客户点的总需求量和车辆装载能力与图1中的例子相同，但各客户需求均由2批(订单)组成(括号内为订单需求量)。采用动态规划算法可分别求得SDVＲP及DSDVＲP在使用最小车辆数且不超载的条件下的最优路径方案。图1SDVＲP最优路径方案Fig．1OptimalsolutiontotheSDVＲP图2DSDVＲP最优路径方案Fig．2OptimalsolutiontotheDSDVＲPDSDVＲP的上述路径方案中，各路径中各包含有3个拆分点，2条路径中公共点个数为3，大于路径数2，总路径长度为10.83，长于SDVＲP总路径长度(9.48)。路径10－1(3)－2(7)－0路径20－1(2)－3(8)－0路径10－1(1)－2(2)－3(7)－0路径20－1(4)－2(5)－3(1)－0对比SDVＲP，DSDVＲP及其最优解具有以下特性(cij、di和Q及其相关限制条件均相同的情况下):1)若Ｒ和Ｒ'分别为SDVＲP和DSDVＲP最优解中任意2条路径间存在的公共点数，存在Ｒ≤Ｒ'，即DSDVＲP最优解中任意两条路径间可能存在多个公共点;2)若L和L'分别为SDVＲP和DSDVＲP最优解中需求拆分点个数，存在L≤L'，即DSDVＲP最优解中拆分点个数可能多于路径数;3)若Z和Z'分别为SDVＲP和DSDVＲP的最优解对应的目标函数值，存在Z≤Z'，即DSDVＲP最优解可能劣于SDVＲP最优解;4)已知SDVＲP为NP－难问题［1，14］，SDVＲP是DSDVＲP的特殊形式，所以DSDVＲP同为NP-Hard问题。2禁忌搜索算法设计2.1解的表达方式本文在算法设计及求解过程的描述中，将各客户的离散需求看成相互独立?
哈尔滨工程大学学报第40卷新路径起点，继续构造新路径。以此类推，直至所有节点均被分配至指定路径为止。2.3同客户节点合并操作由于路径构造时将所有离散的客户订单视为独立节点，故生成的路径中存在同客户订单被分散访问的情况。如图3所示，节点i、j分别表示同客户的不同订单，路径中该客户点被先后访问了2次，增大了不必要的路径成本。为此本文设计同客户订单合并操作，对路径内相同客户的订单进行合并，避免不必要的路径成本，该操作为离散需求拆分的基本路径优化操作，为订单组合的操作奠定基矗图3同客户节点合并操作Fig．3Combinationofitemsfromthesamecustomers2.4同客户节点随机绑定操作一般邻域操作中使用的操作对象为单一的客户节点，因DSDVＲP中的实际个体为各客户订单节点，若简单将客户节点(该客户的全部订单)作为操作对象，则无法体现需求可拆分特性。但若将订单节点作为操作对象，因订单数量远大于客户数，将耗费大量的计算时间。故本文提出一种折中方式，设计同客户节点随机绑定操作，用于邻域操作中实际操作对象的生成及选择。具体操作方式为:在当前解中随机挑选可行的操作对象(节点)，向前向后判断是否存在同客户节点。随后在同客户节点间随机选择若干个连续订单进行绑定，作为接下来邻域操作的实际操作对象。如图4所示，挑选出的操作节点为i，经判断路径中t、i、j、k属于同一客户，t和k分别为起始同客户节点。i、j、k为随机挑选出的连续同客户订单节点，则在下一步邻域操作中将i、j、k绑定视为一个绑定节点i*进行操作。由此可知，经该操作确定的操作对象可能是单一订单节点，如图5;可能是部分订单，如图4和6;也可能是客户点(该客户的全部订单)，如图7，由此增大了操作对象的随机多样性。在?
【参考文献】：
期刊论文
[1]求解需求可拆分车辆路径问题的人工蜂群算法[J]. 姜婷. 四川理工学院学报(自然科学版). 2017(03)
[2]带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 符卓,刘文,邱萌. 中国管理科学. 2017(05)
[3]求解需求可拆分车辆路径问题的聚类算法[J]. 向婷,潘大志. 计算机应用. 2016(11)
本文编号：3570882
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3570882.html
