从京东的物流配送谈车辆路径选择问题

#/88该点时的取货总量之差;等式（2。6）表示送货量等于到达该点时的送货总量与离开该点时的送货总量之差;约束（2.7）为每条路径客户间的容量约束：约朿（2.8）是每辆车的行驶距离约束，L是每辆车的最大行驶距藹;约束（2。9）为决策变量属性。2.5算例分析实验1考虑客户数目较少的情形。1个配送中心给8个客户同时送货和取货,各客户的送货M（id）和取货量为（ip）（单位:吨）由表2o1给岀。这些客户由容量为8吨的3车俩完成配送,汽车的行驶速度设为50km/h,配送中心与各客户间的距离（单位：公里）由表2.2给出。要求合理安排车辆的行驶路线，使总的路径最短.表2.1任务的特征及需求客户/12345678送货吊21.54.531.542.53収货彊31223A1.53表2.2配送中心与各客户之间的距离><0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150（续农）490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000表2.3 10次实验的平均计算结果使用乍辆数（辆〉总路径长度〈km）路径长度的标准差（km）配•辽5案程序运行时间（秒）379000-3-5-1-0：0-8-4-0：0-6-7-2-0：1.5160设置差分进化算法的种群规模NP为40,最大交叉概率maxCR为0°9,最小交叉槪率minCR为0o3,每辆车的最大行驶距离L为400,最大迭代次数为200次，将上述改进的差分进化算法运用MATLAB7.0进行编程，使用Pentiuml、3.06GHz微机运行程序，进行10次实验的平均结果如表2.3,进化结果如图2.1所示。

11OO1050•Chcin^ooroptimumwxmo

Clggwof vRhie1CCC050900S5O800750204060801OO120Haration11OO1050•Chcin^ooroptimumwxmo

Clggwof vRhie1CCC050900S5O800750204060801OO120Haration140ieo180200图2.1经过200次迭代后的运行结果运行200次迭代的程序，10次实验中，10次得到40条染色体表现为相同的配送方案，100%达到最优结果，最终结果为:总的路径长度为790km.使用3俩车完成配送任务，英中第一俩车的配送线路为:0-3-5-1-0,离开配送中心时的实际装载量为8吨，实现满载，回到配送中心时的装载量为8吨，路径长度为215km.第二辆车的配送线路为:0-6-7-2-0,离开配送中心时的实际装载量为8吨，满载率为100%,回到配送中心时的装载量为6。5吨，路径长度为305km。第三辆车的配送线路为:0-8-4-0,离开配送中心时的实际装载屋为6吨，满载率为75%,回到配送中心时的装载量为5吨，路径长度为270km.4小结随着绿色物流兴起和人们环保意识的提高，为了提高售后服务质疑、保护环境、降低物流成本，前向物流和逆向物流的整合必然会变得越来越重要。VRP—SDP有效地整合了前向物流和逆向物流的车辆路径问题，结合VRP-SDP的特征提出其整数规划数学模型，该模型体现了VRP-SDP与VRP之间的理论联系，通过设置不同的参数可以将英转化为VRP.在介绍差分进化算法基本理论的基础上，根据所研究问题的特征,设计一种改进的差分进化算法求解VRP-SDP,这是进化算法在车辆路径问题中的首次应用，改进的差分进化算法采用序数编码，变异操作后采用基于整数序规划的辅助算子,有效解决了变异问题，使变异操作后得到的染色体基因均为序数,能直接进行剩余的其它差分操作，这是设计改进差分进化算法最核心的部分，若采用苴它的取整方法如：四舍五入，向下取整或者向上取整都不能使染色体的所有基因值为序数，即不能得到有效合法的染色体。在交叉操作中设计交叉率随进化代数自动更新的交叉算子，使算法在进化的初始阶段，能提髙算法的全局搜索能力,在进化的后期，能提髙算法的局部搜索能力。最后的算例分析表明，该算法可以在较短的时间内获得该问题的最优解或满意解。由2。3肖可知，通常的(经典的)车辆路径问题比同时送货和取货车辆路径问题简单，故该改进的差分进化算法也能求解其它车辆路径问题。参考文献：|1］刘波，王凌.金以悲。差分进化算法研究进展［J］.控制与决策。2007(07)［2］刘云忠，宜慧玉. 乍辆路径问题的模型及算法研究综述［J］.管理工程学报.2005(01)|3］张建勇，李军。具有同时配送和回收需求的车辆路径问题的混合遗传算法［J］。中国公路学报.2006(04)［4］方强。 基于优进策賂的差分进化算法及其化匸应用［D］<,浙江大学.2004［5］曹二保.物流配送年辆路径问題模型及算法研尤［D|.湖南大学。2008|6］瑰琼杰，袁翊茗.