一种时变路网下考虑时空距离的车辆路径优化方法

摘要

本发明提供一种时变路网下考虑时空距离的车辆路径优化方法，包括：获取车辆行驶速度连续动态变化信息，通过三角函数拟合速度时间依赖函数；以车辆派遣成本、车辆运输成本以及时间窗惩罚成本之和最小化为目标建立同时配集货车辆路径优化模型；将客户的服务时间和空间位置相结合计算时空距离，并基于所述时空距离生成初始种群，在遗传算法基础上嵌入三种邻域结构，设计考虑时空距离的混合变邻域搜索遗传算法求解所述同时配集货车辆路径优化模型，从而获取车辆路径优化方案。本发明以配集货总成本最小化为目标建立综合考虑客户服务时间，空间位置以及配集货需求的优化模型，能够更加客观准确的反映真实物流系统的运行情况。

说明书

技术领域

本发明涉及时变路网下同时配集货车辆路径问题、带时间窗的车辆路径问题等领域，具体而言，尤其涉及一种时变路网下考虑时空距离的车辆路径优化方法。

背景技术

目前，针对时变路网下车辆路径问题的研究，多基于阶跃函数表示道路速度变化而没有考虑车辆行驶速度是连续变化的。在同时配集货车辆路径问题的研究领域，如果不考虑车辆行驶速度连续动态变化对配送方案的影响，将导致优化结果不能适应实际的道路交通状况。此外，在同时配集货车辆路径优化算法收敛变慢且最优解的质量较差，也不能满足实际的应用需求。

发明内容

根据上述提出的以阶跃函数表示速度变化导致的路径优化结果较差的技术问题，而提供一种时变路网下考虑时空距离的车辆路径优化方法。本发明主要利用采用三角函数拟合速度时间依赖函数，以配集货总成本最小化为目标建立综合考虑客户服务时间，空间位置以及配集货需求的优化模型，能够更加客观准确的反映真实物流系统的运行情况。

本发明采用的技术手段如下：

一种时变路网下考虑时空距离的车辆路径优化方法，包括：

获取车辆行驶速度连续动态变化信息，通过三角函数拟合速度时间依赖函数；

以车辆派遣成本、车辆运输成本以及时间窗惩罚成本之和最小化为目标建立同时配集货车辆路径优化模型；

将客户的服务时间和空间位置相结合计算时空距离，并基于所述时空距离生成初始种群，在遗传算法基础上嵌入三种邻域结构，设计考虑时空距离的混合变邻域搜索遗传算法求解所述同时配集货车辆路径优化模型，从而获取车辆路径优化方案。

进一步地，获取车辆行驶速度连续动态变化信息，包括：获取车辆行驶速度历史数据；根据车辆行驶速度全天变化趋势确定车辆行驶速度连续动态变化函数。

进一步地，时间窗惩罚成本包括早到时间惩罚成本和晚到时间惩罚成本。

进一步地，将客户的服务时间和空间位置相结合计算时空距离，并基于所述时空距离生成初始种群，包括：

首先计算客户间的时空距离，以每一个聚类簇中其他客户到该聚类簇中心的时空距离之和最小为目标，将时空距离相近的客户进行聚类，生成聚类簇；将聚类簇内的客户按其与配送中心的距离进行排序，选择相应车型进行路径的划分，从而生成初始种群。

进一步地，在遗传算法基础上嵌入三种邻域结构，并引入自适应邻域搜索次数策略，设计考虑时空距离的混合变邻域搜索遗传算法求解所述同时配集货车辆路径优化模型，包括：

对客户进行编码与解码操作生成染色体，包括采用整数编码的形式，对客户进行随机全排列，根据车辆返回配送中心时刻以及容量约束将顾客按照初始排列顺序划分给车辆，当对下一个客户进行检验发现当前车辆不能满足要求时，选择不同容量的车型对该客户进行服务；

根据模型中目标函数构造染色体的适应度函数；

选择操作采取轮盘赌与精英保留相结合的选择策略，首先采用轮盘赌的方式选择染色体，再采用精英保留策略，将每一代的最优染色体进行保留；

选用顺序交叉算子对染色体进行进化操作；

选用插入、交换和2-OPT三种邻域结构对种群进行局部搜索，获得最优解。

进一步地，选用插入、交换和2-OPT三种邻域结构对种群进行局部搜索，获得最优解，包括：根据种群迭代自适应调整邻域搜索次数。

较现有技术相比，本发明具有以下优点：

1、本发明以配集货总成本最小化为目标建立综合考虑客户服务时间，空间位置以及配集货需求的优化模型，能够更加客观准确的反映真实物流系统的运行情况，所得出的车辆调度优化方案可以有效的降低配送中心的运营成本。

2、本发明设计的考虑时空距离的混合变邻域搜索遗传算法，先通过计算客户间时空距离对客户进行时空聚类后生成的初始种群，有效提高了初始解的质量，使结果更优。

3、本发明算法在选择操作时采取精英保留和轮盘赌相结合的策略，保证了算法的有效收敛。并且使用进化操作和自适应搜索机制，改善了局部搜索能力，提高了求解质量，求得的结果具有较好的稳定性。

基于上述理由本发明可在物流配送及路径规划领域广泛推广。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图做以简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为实施例中时变路网下考虑时空距离的车辆路径优化方法流程图。

图2为实施例中车辆行驶速度全天变化趋势图。

图3为实施例中时空路径图。

图4为实施例中编解码示意图。

图5为实施例中顺序交叉算子示意图。

图6为实施例中邻域结构示意图。

图7为实施例中配送路网图。

图8为实施例中车辆速度时间依赖函数图。

图9为实施例中最优配集货路线图。

具体实施方式

为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。

需要说明的是，本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

如图1所示，本发明实施例提供了一种时变路网下考虑时空距离的车辆路径优化方法，包括：

S1、获取车辆行驶速度连续动态变化特征，通过三角函数拟合速度时间依赖函数。

具体来说，将一天中道路速度连续变化情况用多个三角函数关系式近似表示，速度(v)与时间(t)之间的三角函数关系表达式可表示如下：

其中参数a

车辆行驶速度全天变化趋势，如图2所示。车辆k从节点i出发的时刻为

S2、以车辆派遣成本、车辆运输成本以及时间窗惩罚成本之和最小化为目标建立同时配集货车辆路径优化模型。

具体来说，本实施例中针对的问题是时变路网下考虑时空距离的同时配集货车辆路径问题，具体表述如下：假设有完备的有向图G＝(V,E)，有不同类型的道路，每种类型的道路车辆行驶速度v是连续变化的；节点集合为V＝V

模型具体如下：

s.t

其中，式(2)表示目标函数，是以车辆派遣成本、车辆运输成本、时间窗惩罚成本之和最小化为目标；式(3)表示每个客户只能被车辆服务一次；式(4)表示车辆的进出平衡约束；式(5)表示车辆被使用时只有一条服务路径且车辆完成任务后必须返回配送中心；式(6)表示车辆访问客户p前后的车辆装载量平衡约束；式(7)表示车辆在服务客户j之后的车载容量约束；式(8)表示车辆初始载量；式(9)表示配集货过程中配送中心使用的车辆不超过其车辆数量限制；式(10)表示车辆从客户i到达客户j的时刻；式(11)表示相同节点之间没有通路；式(12)为消除子回路约束；式(13)确保任意车辆返回配送中心的时刻不超过配送中心截止工作时刻；式(14)和(15)为模型决策变量属性。

S3、将客户的服务时间和空间位置相结合计算时空距离，并基于所述时空距离生成初始种群，在遗传算法基础上嵌入三种邻域结构，设计考虑时空距离的混合变邻域搜索遗传算法求解所述同时配集货车辆路径优化模型，从而获取车辆路径优化方案。

具体来说，遗传算法具有鲁棒性、并行性高和搜索能力强的特点，但收敛速度慢且容易陷入局部最优，不能保证整体最优。变邻域搜索算法采用多个不同的邻域结构进行系统搜索，具有较强的局部搜索能力。因此结合遗传算法和变邻域搜索算法，并在此基础上首先根据配送中心以及客户的时空距离进行客户分组和聚类，从而生成较好的初始种群，设计了考虑时空距离的混合变邻域搜索遗传算法，将变邻域搜索算法应用到遗传算法的局部搜索策略中，以增强算法的寻优能力。主要步骤包括：

(1)客户聚类以及初始种群生成

将时空距离相近的客户进行聚类，生成聚类簇，同一聚类簇内客户的时空距离较近，不同聚类簇间的客户时空距离较远。聚类的方法如式(16)所示，目的是使每一个聚类簇中其他客户到该聚类簇中心的时空距离之和G最小，式中u为聚类簇的数目，

最后将聚类簇内的客户按其与配送中心的距离进行排序，灵活选择合适的车型进行路径的划分，最终的路径可在三维图中形象的刻画出来，如图3所示。纵坐标代表时间，平面二维坐标代表空间位置，0表示配送中心，A、B、C、D、E表示客户，圆柱表示时间窗。时空路径1为O

(2)编码与解码

采用整数编码的形式，例如有9个客户，1个配送中心，则数字1-9表示客户，对客户进行随机全排列，数字0表示配送中心。解码时根据车辆返回配送中心时刻以及容量约束将顾客按照初始排列顺序划分给车辆，当对下一个客户进行检验发现当前车辆不能满足要求时，灵活选择不同容量的车型对该客户进行服务。且每辆车服务的第一个客户前插入0，即从配送中心出发。本文以一个简单例子来进行说明，如图4所示，假设客户的全排列顺序为1、5、8、3、4、6、9、2、7，派第一辆车对客户1进行服务，当服务客户4时不满足约束，则第一辆车的路径为1-5-8-3，选用车型1。以此类推，第二辆车的路径为4-6，选用车型2，第三辆车的路径为9-2-7，选用车型1。

(3)适应度评价

染色体的适应度函数可以根据模型中目标函数式(2)进行构造。染色体K的适应度函数f

本实施例中，目标函数为总配送成本最小化，优化的目标就是选择适应度函数值较大的染色体。其中，z

(4)选择操作

选择操作采取轮盘赌与精英保留相结合的选择策略。采用轮盘赌的方式，每条染色体被选中的概率与其适应度函数值的大小成正比，即适应度函数值越高的染色体被选中的概率就越高；反之，则被选中的概率越低。在选择操作结束后，采用精英保留策略，将每一代的最优染色体进行保留，即用上一代适应度值最优的个体替换掉子代适应度值最差的个体。采用轮盘赌和精英保留相结合的策略，保证种群规模始终不变且使算法快速收敛。

(5)进化操作

本文的进化操作选用顺序交叉算子。如图5所示，对于父代Pop1进行顺序交叉时，从种群中随机选取父代Pop2，首先分别随机产生点位i

(6)局部搜索优化

选用插入、交换和2-OPT三种邻域结构对种群P(t)进行局部搜索，三种邻域结构示意图如图6所示，局部搜索操作伪代码如下：

作为本发明的优选实施方式，本实施例还设计了自适应邻域搜索次数策略以增强算法搜索的广度和深度，使变邻域搜素算法能够跳出局部最优。邻域搜索次数对算法的搜索能力具有较大的影响，直接导致了算法性能的优劣。在算法迭代的过程中，种群所需的扰动强度不同，在迭代初期，邻域搜索次数应当较小，使种群快速收敛；而随着种群的不断迭代，增加邻域搜索次数，加强算法的搜索能力。S

式中，S

下面通过具体的应用实例，对本发明的方案和效果做进一步阐述。

通过图1流程图可知，首先考虑车辆行驶速度连续动态变化，采用三角函数拟合速度时间依赖函数。然后以车辆派遣成本、车辆运输成本、时间窗惩罚成本之和最小化为目标建立同时配集货车辆路径优化模型。在对模型求解时，将客户的服务时间和空间位置相结合计算时空距离，并以此生成初始种群，在遗传算法基础上嵌入三种邻域结构，并引入自适应邻域搜索次数策略，设计考虑时空距离的混合变邻域搜索遗传算法求解所建立模型。

算例含有一个配送中心和50个客户，客户的配、集货量由需求分离规则产生：x

表1不同车型费用参数

如图7所示，该实验将配送路网中的道路划分为主干路、次干路以及支路三种类型，其中红色线路代表主干路，其速度为v

利用本文设计的考虑时空距离的混合变邻域搜索遗传算法进行求解，得到最优的配集货方案，配集货路线图如图9，具体配送方案见表2。

表2最优配集货方案

由表2可以得出配送中心派出6辆车对这50个客户进行服务，其中容量为60、100和120的车各2辆，将其成本相加可得配集货总成本为3422.77。

上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

在本发明的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

在本申请所提供的几个实施例中，应该理解到，所揭露的技术内容，可通过其它的方式实现。其中，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，可以为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。