龙源期刊网 http://www.qikan.com.cn
电子商务环境下路径优化模型及算法研究
作者：王绍凡 陈荔
来源：《软件导刊》2017年第08期
摘 要：研究了电子商务环境下有时间窗的车辆路径问题，考虑了时间窗限制的约束，并构建以最小成本为目标的模型，包括固定成本、运输成本和惩罚成本。为求解所建模型，提出了基于改进智能水滴算法的车辆路径优化方案，并进行了程序设计。运用算法实例进行验证，并将算法结果进行对比分析，表明改进的算法收敛性更好，能求出问题的最优解。 关键词：电子商务；时间窗；物流配送；车辆路径问题；智能水滴算法 DOIDOI：10.11907/rjdk.171130 中图分类号：TP312
文献标识码：A 文章编号文章编号：1672-7800（2017）008-0032-04 0 引言
电子商务模式受到越来越多的关注。在电子商务环境下，如何合理设计配送路线、提高效率、减少物流成本是急需解决的问题。
随着信息技术和云计算的发展，形成了新的物流配送模式，学者对其形式及现状进行了探索。郎茂祥[1-3]分别用遗传、模拟退火和禁忌搜索等算法对一般VRP和有时间窗的VRP问题进行求解。何云等[4]以成本最低为目标并加入客户时间满意度构建模型，运用遗传算法求解获得最优配送路径。TC Du等[5]针对电子商务B2C环境下的动态车辆路径问题设计了模型算法求解。侯玉梅等[6]构建了有时间窗的模型并求解。与传统算法相比，智能水滴算法是根据自然界中水滴与所处环境之间相互作用产生河道过程的一种智能算法，最先被Hamed Shah-Hosseini[7]用于解决旅行商问题，最终收敛得到最优解。随后智能水滴算法用于解决旅行商问题、多维背包问题和灰度阈值问题等[8-10]。马竹根[11]介绍了IWD的产生原因，阐述了多种领域应用并进行总结。Iman Kamkar等[12]运用智能水滴算法求解一般车辆问题。徐佳敏等[13]将智能水滴算法运用到求解应急物流问题中并得到优化结果。周虹[14]和李珍萍[15]针对有时间窗问题运用智能水滴算法求解。
本文研究了电子商务环境下的VRP问题，基于改进智能水滴算法建立总成本最小模型，利用该算法求解最优路线，并结合算例进行了验证与分析。 1 配送路径问题描述及模型
龙源期刊网 http://www.qikan.com.cn
电子商务环境下的带时间窗车辆路径优化问题可描述为：从一个配送中心出发为多个顾客进行服务，且车辆在配送任务结束后需返回出发点。假设配送车辆的型号一致并且最大承载量一定，顾客所需求的数量以及配送中心和顾客位置已知，并且顾客对于服务时间有限制。因此，本文就是在满足一系列约束条件下，设计合理的配送路线的目标优化问题。
令G=（N，S）为客户点和配送中心及客户之间连线所组成的无向路线图，N表示需要配送的客户集合，其中N={1，2，…，n}，0表示配送中心，S表示连线所组成的边集合，K表示配送中心车辆总数，ri表示顾客需求量，ωk表示车辆的最大承载量，Fk表示运输车辆的固定成本，cij表示车辆k在顾客i与j之间的运输成本，dij表示顾客与顾客之间及配送中心与顾客之间的距离，Tij表示车辆从顾客i到j的行驶时间，Tik表示车辆k到达顾客i的时间，ti表示为顾客i开始服务的时间，m1为提前到达等待的惩罚系数，m2为延迟到达的惩罚系数；vk表示车辆的平均行驶速度，[ATi，BTi]表示顾客i所期望的服务时间，[ETi，LTi]表示顾客i可接受的服务时间（ETi 定义模型的决策变量：
xkij=1车辆k从顾客i驶向顾客j；i，j=1，2，…，n；0否则；k=1，2，…k；（1） yki=1车辆k对顾客i服务；i，j=1，2，…，n；0否则；k=1，2，…k； （2）
基于以上描述及假设，针对时间约束条件，增加惩罚函数，建立总成本最小的目标优化模型如下：minZ1=∑Kk=1∑Ni=1∑Nj=1cijdijxkij+∑Kk=1∑Nj=1Fkxk0j+m1∑Ni=1max（ATi-ti，0）+m2∑Ni=1maxti-BTi，0（3）s.t. ∑Ni=1riyki≤ωk ∑Ni=1∑Nj=1dijxkij≤D ∑Kk=1yki=1i=1，2，…，n ∑Nj=1xk0j=1；∑Ni=1xki1=1
∑Ni=1xkij=ykjj=1，2，…，n；k=1，2，….k ∑Nj=1xkij=ykii=1，2，…，n；k=1，2，…k
假定：①任何车辆所运送的客户总需求量不能超过车辆的最大载重量；②每台车的行驶运输距离不大于车辆的最长运输距离；③每位顾客只能由一辆车辆进行配送；④每台配送车辆都由配送中心出发；⑤每台车辆任务完成后都需要回到配送中心；⑥配送车辆完成当前配送任务后，为下一位顾客继续提供服务约束。 2 算法求解
龙源期刊网 http://www.qikan.com.cn
2.1 智能水滴算法
G=（N，S）为客户点和配送中心及客户点之间连线所组成的无向路线图，表示电子商务环境下的车辆路径问题。其中，N表示需要配送的客户集合，其中N={1，2，…，n}，0表示配送中心；S表示连线所组成的边集合，即客户点之间的距离。
将水滴运动时所携带的泥土量设为soil（IWD），水滴向前行驶时的速度设为velocity（IWD）。在水滴运动时这两项都在不断变化，算法就是在其中找到一条最优路径，相当于解决实际优化问题。
每个水滴从起始点出发相当于配送车辆从配送中心出发，并从满足所有约束条件的顾客集合中，按照概率公式选择出服务的下一位顾客，所有服务完成后必须回到配送中心。这个运行过程可形成多个闭合的配送回路。算法运行过程中所得的最优解，需要用构造的目标函数来确定。每次迭代结束后都可在完整的访问路线中找到最优解，定义为TIB，并用这个最优解来替换每个节点之间的泥土量以及全局最优解TTB。重复运行这一过程，直到期望的最优解TTB产生或算法运行到最大迭代次数Itermax。
水滴从所处位置i流动到下一位置j，它的速度增加值设定为Δvelocity（IWD），它与两者之间路径上的泥土量相关，表示为：
Δvelocity（IWD）=ΔvelIWD（t）=avbv+cv·soil（i，j）（4） av、bv、cv分别为水滴速度的更新参数。
水滴中泥土的增加量Δsoil（IWD）与水滴在相邻两点间运动所耗费的时间相关，这一时间是以水滴的流速表示的，即time（i，j；velIWD）。因此，泥土的增加量表示为： Δsoil（IWD）=Δsoil（i，j）=asbs+cs·time（i，j；velIWD）（5）
as、bs、cs分别为大于0的参数。智能水滴相邻两点间的时间可根据物理学中的匀速直线运动公式计算，即由两节点间的距离与行驶速度计算： time（i，j；velIWD）=D（i，j）velIWD（6）
智能水滴从位置i运动到位置j的过程中，会带走一定数量的泥土，可由智能水滴所带走的泥土数量（Δsoil（i，j））来更新，其表达式为： soil（i，j）=ρ0·soil（i，j）-ρn·Δsoil（i，j）（7）
在式（7）中，ρ0和ρn通常都会选择0-1之间的正数，并且两者之间满足关系式ρ0=1-ρn。