1.一种带时间窗的冷链物流路径优化方法,其特征在于,包括以下步骤:
第一步:依据异构车辆的多类车型问题,扩充现有SOLOMN算例中的车辆类型参数并读取算例的任务:需要常温车辆服务的客户n个,需要带有冷藏装置的车辆服务的客户m个,车辆类型K种,货物需求量,0-1变量约束表示客户i可以由车辆类型K进行运输到客户j,问题的约束条件是:每个客户只能由一辆车进行服务,每辆车的负载不能超过其最大负载;提供服务的车辆必须在配送中心开始和结束,同时该车辆在配送中心时前面和后面的节点均不超过一个;
第二步:确定优化的目标及约束条件:
公式中 是车辆类型k启用的固定成本,车辆类型k的耗能指标;tij是车辆从i到j所花费的时间,svi是客户满意度,α,β是系统参数;
第三步:提出一种星级评定的方式确定客户满意度;
步骤1:当服务车辆在严格时间窗到达并服务,客户i差评等级评定bvi=0,客户满意度svi=5;
步骤2:当服务车辆在提前松弛时间窗到达,客户i差评等级评定
客户满意度svi=5-bvi;
步骤3:当客服务车辆在延迟松弛时间窗内到达,客户i差评等级评定
客户满意度svi=5-bvi;
第四步:提出一种车辆等待方案提高客户满意度;
步骤1:对于给定的解决方案,检查所有车辆,对于每个车辆执行以下步骤;
步骤2:对于每一辆车,从右到左,找到第一个客户i,让车在最早的左侧松弛时间窗等待;
步骤3:对于车辆k,发现顾客j满足以下条件:(1)顾客j在i之前;(2)j的开始服务时间在左侧松弛时间窗口,在严格时间窗口之前,即j的开始服务时间可以右移,提高客户满意度;
步骤4:对每个车辆重复步骤2和步骤3;
第五步:采用改进的人工鱼群算法优化路径解决方案:
步骤1按照扩充的SOLOMN算例,循环生成X=(x1,x2,...,xm)共m个初始解存入当前解集;
步骤2鱼群觅食行为:第一,循环初始解集的每一个解xi,根据“可视范围”确定解的邻域解集;第二:如果当前解xi在“可视范围”内随机选择一个解xj,如果xj的目标值比xi优秀,则xi向xj方向移动,即xi与xj进行交叉操作;第三:在公告板更新最好解;第四:更新xi的尝试次数try_number;
步骤3鱼群追尾行为:第一:循环初始解集的每一个解xi,根据“可视范围”确定解的邻域解集;第二:如果“可视范围”内存在最优解xbest,当xi周围不是很拥挤,且xbest的目标值比xi优秀,则xi向xbest移动,即xi与xbest进行交叉操作;第三:在公告板更新最好解;第四:如果移动不成功,则执行觅食行为;
步骤4鱼群随机行为:在“可视范围”内随机选择一种状态并向该状态移动,交叉策略如下:第一:选择当前解xi的普通车辆部分,选择“可视范围”内最优解xbest的冷链车部分,将两部分组合起来;第二:如果xi的冷链车数量大于xbest的冷链车数量,则全部复制,删去多于车i best辆;第三:选择当前解x的冷链车辆,选择“可视范围”内最优解x 的普通车部分,将两部分组合起来;第四:如果xbest的冷链车数量大于xi的冷链车数量,则全部复制,删去多于车辆;
第五:原有目标值与重组后目标值进行比较,将最好解更新至公告板;
第六步:将所述路径优化方案下发到各个配送车辆。
2.根据权利要求1所述的一种带时间窗的冷链物流路径优化方法,其特征在于:所述第五步中的步骤1按照扩充的SOLOMN算例,利用改进的PFIH策略IPFIH,循环生成m-1个初始解,再利用PFIH策略生成一个初始解,初始解存入当前解集,所述步骤1中的编码策略如下:采用二维数组的方式编码一个解,二维数组的第一维表示每一辆车,前25个表示常温车型,后25个表示冷藏车型,对于每辆车创建一个数组,包含该车辆服务的客户序列,客户序号的先后顺序表示这些客户点的服务次序。
3.根据权利要求2所述的一种带时间窗的冷链物流路径优化方法,其特征在于:所述具体的IPFIH初始化算法步骤如下:步骤1,设置IPFIH迭代终止条件m-1,并将当前所有客户随机排序;步骤2,循环每一个客户j,并设置当前最好插入位置mp=0,设置mv=L,L为极大值;
步骤3,如果当前客户j可以插入当前车辆i中,则循环当前车辆i的所有可以插入客户j的位置,计算客户j插入当前车辆所有位置的费用,找到费用最小的位置pj,即如果j作为下一个安排服务的客户则其插入位置为pi,客户j插入到车辆i的位置u的费用计算如下所示:c1(k,u,h)=α1c11(k,u,h)+α2c12(k,u,h),α1+α2=1,α1,α2≥0;
c11(k,u,h)=tku+tuh-μtkh,μ≥0
c12(k,u,h)=wh'-wh,
式中,k和h表示当前车辆上位置u-1和u的客户,wh'表示插入客户j 到位置u后,客户h的开始服务时间,μ为系统参数,步骤4,如果c1(k,u,h)<mv,则mv=c1(k,u,h);mp=u,将当前客户j插入当前车辆i的mp位置上;步骤5,否则,如果当前车辆数目未超过最大车辆数限制,则添加一辆新车;如果当前车辆数已满,则丢弃该解;步骤6,将产生好的m-1个解存入初始解集。
4.根据权利要求3所述的一种带时间窗的冷链物流路径优化方法,其特征在于:IPFIH初始化算法总体流程如下:步骤1,循环所有剩余未调度的客户点,计算每个客户j插入当前车辆i的所有位置的费用,找到费用最小的位置pj,即如果j作为下一个安排服务的客户则其插入位置为pj,客户j插入到车辆i的位置u的费用计算同权利要求3内的公式;步骤2,计算每个客户的c2值,找到最小c2值的客户j*,记为下一个服务的客户点,计算如下:式中,Rd(u)和Rt(u)分别表示在位置u插入新的客户点j*后,车辆i的总路径费用和部分路径时间代价,步骤3,将当前解存入初始解集。
5.根据权利要求1所述的一种带时间窗的冷链物流路径优化方法,其特征在于:鱼群觅食行为中当前解xi的产生策略I:步骤1:为了生成邻域解,随机选择一种车型,对所选车型随机选择一辆车,然后从中随机选择一个客户,并将其在所选车辆中删除,步骤2:将所选客户插入到同类型的另一辆车中,鱼群捕食行为中当前解xi的产生策略II:步骤1:为了生成邻域解,与策略I相同,随机选择一辆车,然后从所选车辆中随机选择一定数量的客户并将这些客户从当前车辆中删除,步骤2:将选择的客户随机插入到相同车型的其他车辆中。