1.一种基于现实交通环境的城市配送车辆路径优化方法,其特征在于,包括以下步骤:S1、暂不考虑从分拨中心到配送中心和从配送中心到客户两个阶段的车辆路径,将基于现实交通环境的城市配送车辆路径优化问题简化成两阶段设施选址问题,以物流服务总成本最小化为目标函数,以满足所有客户的物流需求和配送中心的作业能力限制为约束条件建立两阶段设施选址模型,求解得到配送中心的选址方案和客户的分配方案;
S2、基于步骤S1得到的配送中心选址方案和客户分配方案,结合现实的城市交通环境,将基于现实交通环境的城市配送车辆路径优化问题转化为若干个随机多路径车辆路径问题,再将被选用的配送中心以及分配给每个被选用配送中心的客户根据配送车辆的额定载重进行分组,进一步将每个随机多路径车辆路径问题转化为若干个随机多路径旅行商问题,并对每个随机多路径旅行商问题建模;
S3、将步骤S2得到的每个随机多路径旅行商问题转化为相应的近似确定型规划问题,并对其进行求解,通过整合所有随机多路径旅行商问题的求解结果,得到基于现实交通环境的城市配送车辆的最优路径;具体的:每个随机多路径旅行商问题转化为如下的近似确定型规划问题:目标函数:
约束条件:
其中,β表示路径集Pij中路径的分散程度,表示为:|Pij|表示点i与j之间路径的数量;fD表示以任意两点之间最短路构成的旅行商问题的目标函数值,|V|表示V中点的个数,b表示V中任意两点之间最短路的通行成本,V表示分拨中心与被选用的配送中心或某一被选用的配送中心及其被分配的客户组成的点集;V′表示V的非空真子集;E表示V中任意两点组成的边集;Pij表示V中点i与j之间的路径集;参数表示点i与j之间路径p的随机通行成本,其中表示点i与j之间路径p的固定通行成本,表示路径p固定通行成本的随机波动;决策变量Xij表示配送车辆是否通过点i到达点j,若是则取值为1,否则取值为0;
求解上述近似确定型规划问题,得到随机多路径旅行商问题路径方案Xij的最优值以及的最优值表示配送车辆是否经过路径p从点i到达点j,若是则取值为1,否则取值为0;当取值为1时,若点i与j之间路径p的通行成本最小,则取值为1,否则为0。
2.根据权利要求1所述的一种基于现实交通环境的城市配送车辆路径优化方法,其特征在于,步骤S1中两阶段设施选址模型为:目标函数:
约束条件:
其中,S表示配送中心的备选集;C表示客户集;参数fs、ws分别表示配送中心s的启用成本和作业能力,s∈S;dc表示客户c的物流需求量,c∈C;H0s表示分拨中心与配送中心s之间最短路的单位运输成本;Hsc表示配送中心s与客户c之间最短路的单位运输成本;决策变量Zs表示配送中心s是否被选用,若被选用则取值为1,否则取值为0;usc表示客户c是否由配送中心s提供服务,若是则取值为1,否则取值为0。
3.根据权利要求1所述的一种基于现实交通环境的城市配送车辆路径优化方法,其特征在于,步骤S2中采用具有约束的K-means算法将被选用的配送中心以及分配给每个被选用配送中心的客户根据配送车辆的额定载重进行分组;具有约束的K-means算法流程为:(1)输入原始数据:包括每个需求点的经纬度坐标、每个需求点的物流需求量以及配送车辆的额定载重Q;需求点是指被选用的配送中心或分配给某个被选用配送中心的客户;
(2)初始化参数:包括质心的数量dc表示客户c的物流需求量,每个质心的服务能力为Q,随机选择K个需求点的经纬度坐标作为K个质心的初始坐标;质心是指一组需求点经纬度坐标的均值所表示的点;
(3)将需求点按物流需求量从大到小降序排列;
(4)按顺序将需求点逐一分配给距其最近且有剩余服务能力的质心;
(5)若所有需求点完成分配,则转入步骤(6),若有需求点无法进行分配,则令K=K+1,反复执行步骤(2)~步骤(4),直至所有需求点完成分配;
(6)更新每个质心的坐标,即用每个质心所服务需求点的经度、纬度坐标的均值代替其当前经度、纬度坐标;
(7)重复执行步骤(2)~步骤(6)设定次数,返回分组结果,其中每个质心所服务的需求点划为一组。
4.根据权利要求1所述的一种基于现实交通环境的城市配送车辆路径优化方法,其特征在于,步骤S2中每一个随机多路径旅行商问题建模如下:目标函数:
约束条件:
其中:
约束条件:
5.根据权利要求1所述的一种基于现实交通环境的城市配送车辆路径优化方法,其特征在于,步骤S3中随机多路径旅行商问题的目标函数值,通过如下的蒙特卡洛仿真步骤获得:(1)随机生成包含若干种交通环境情景的情景集Φ以及在情景下路径p固定通行成本的随机波动值(2)根据求得的最优解按下式计算与随机多路径旅行商问题等价的情景规划问题在情景下的目标函数值其中:
表示点i与j之间路径p在情景下的随机通行成本,其中表示点i与j之间路径p的固定通行成本;
(3)再根据步骤(2)求得的按下式计算随机多路径旅行商问题的目标函数值fDAP:其中,表示情景发生的概率;
(4)重复步骤(1)~步骤(3)设定次数,并返回fDAP的值。
6.一种基于现实交通环境的城市配送车辆路径优化系统,其特征在于,包括:两阶段设施选址问题建立模块,用于在不考虑从分拨中心到配送中心和从配送中心到客户两个阶段车辆路径的情况下,将基于现实交通环境的城市配送车辆路径优化问题简化成两阶段设施选址问题,求解得到配送中心的选址方案和客户的分配方案;
随机多路径车辆路径问题建立模块,用于在得到的配送中心选址方案和客户分配方案的情况下,结合现实的城市交通环境,将基于现实交通环境的城市配送车辆路径优化问题转化成若干个随机多路径车辆路径问题;
随机多路径旅行商问题建立模块,用于将被选用的配送中心以及分配给每个被选用配送中心的客户根据配送车辆的额定载重进行分组,进一步将每个随机多路径车辆路径问题转化成若干个随机多路径旅行商问题;
近似确定型规划问题求解模块,用于将得到的每个随机多路径旅行商问题转化为相应的近似确定型规划问题,并进行求解;具体的:每个随机多路径旅行商问题转化为如下的近似确定型规划问题:目标函数:
约束条件:
其中,β表示路径集Pij中路径的分散程度,表示为:|Pij|表示点i与j之间路径的数量;fD表示以任意两点之间最短路构成的旅行商问题的目标函数值,|V|表示V中点的个数,b表示V中任意两点之间最短路的通行成本,V表示分拨中心与被选用的配送中心或某一被选用的配送中心及其被分配的客户组成的点集;V′表示V的非空真子集;E表示V中任意两点组成的边集;Pij表示V中点i与j之间的路径集;参数表示点i与j之间路径p的随机通行成本,其中表示点i与j之间路径p的固定通行成本,表示路径p固定通行成本的随机波动;决策变量Xij表示配送车辆是否通过点i到达点j,若是则取值为1,否则取值为0;
求解上述近似确定型规划问题,得到随机多路径旅行商问题路径方案Xij的最优值以及的最优值表示配送车辆是否经过路径p从点i到达点j,若是则取值为1,否则取值为0;当取值为1时,若点i与j之间路径p的通行成本最小,则取值为1,否则为0;
最优路径求解模块,用于通过整合所有随机多路径旅行商问题的求解结果,得到基于现实交通环境的城市配送车辆的最优路径。
7.一种装置设备,其特征在于,包括存储器和处理器,其中:
存储器,用于存储能够在处理器上运行的计算机程序;
处理器,用于在运行所述计算机程序时,执行如权利要求1-5任一项所述一种基于现实交通环境的城市配送车辆路径优化方法的步骤。
8.一种存储介质,其特征在于,所述存储介质上存储有计算机程序,所述计算机程序被至少一个处理器执行时实现如权利要求1-5任一项所述一种基于现实交通环境的城市配送车辆路径优化方法的步骤。