有道路限行的集团蔬菜城市配送车辆路径问题.pdf

《有道路限行的集团蔬菜城市配送车辆路径问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上l海管理科学ShanghaiManagementScience第35卷第5期l2013年10,EJIVo1．35lNo．5IOctober．2013文章编号：1005—9679(2013)05．0038—08有道路限行的集团蔬菜城市配送车辆路径问题赵璐赵磊朱道立(1．上海交通大学中美物流研究院；2．上海交通大学安泰经济与管理学院)摘要：本文研究服务于消费集团的城市蔬菜配送企业的车辆路径优化(VRP)问题，此类VRP问题有如下特征：(1)消费集团客户集中分布在城市中心区域，(2)配送车辆需要受到城市中心区域道

2、路限行的约束，(3)客户需求时间窗集中，(4)蔬菜是易腐食品，并有新鲜度的要求。本文以最低配送成本为目标，综合考虑客户满意度和蔬菜新鲜度要求，建立了有道路限行的多车型带客户需求时间窗的vRP问题的数学模型，并设计了一种遗传算法求解。求解结果表明该算法可以有效计算最优车辆路径、出发时间、不同的客户分布所需要的车型组合以及相应的最低成本，为企业的日常运营、车型配置和服务定价提供决策支持。关键词：城市蔬菜配送；道路限行；车辆路径优化问题；多车型组合；遗传算法中图分类号：F253文献标志码：A1问题描述及数学模型{0

3、，．．．，埘：车型集合；本文研究有道路限行的多车型带客户需求时2．参数：间窗的VRP问题，即存在一个配送中心，配送中g：节点i∈的配送需求，q。=0；心有不同类型的车辆参与配送服务，而且车辆没：节点i∈的卸货时间，do=O；有数量限制。车辆从配送中心出发，为分布在不：k型车辆(k∈)的载货能力；k同区域的客户服务，每个客户只能由一辆车服务，10i：k型车辆(∈)在弧(f，)∈A上的运且只能服务一次，车辆完成配送服务后回到配送行成本；k中心。配送中心24小时不间断服务，每个客户：k型车辆(k∈)在弧(f，)∈上

4、的行有自己的需求时间窗，当车辆开始服务的时间晚驶时间；于客户需求时间窗上限时，会影响到客户满意度。[口，a]：k型车辆(k∈)允许在弧(f，)∈不同类型的车辆在不同的区域受到不同道路限行上行驶的时间窗；的约束且每条路线上的客户总需求量不得超过该[e，，节点i的客户需求时间窗，且规定一ei口；条路线所选车型的载货能力。模型的最终目标为，找到具有最低配送成本、最高客户满意度和最高FC：k型车辆(k∈)的固定成本；蔬菜新鲜度的配送路径方案并包括车型选择和服：客户满意度要求；务时间调度。为了更好地实现资源的优化配置，

5、：蔬菜新鲜度要求；本文采取增加约束条件的方法进行多目标处理，：一个很大的常数；即将客户满意度和蔬菜新鲜度转化为约束条件。3．决策变量：本文研究的问题可以被定义在一个联通图中：如果弧(f，由k型车辆(七∈)服务，G一(，)，模型中的参数定义如下：贝U一1，否贝U《：==0；1．集合：U：节点i的开始服务时间；{0，．．．，胛}：节点集合，其中节点0为配送中Y：弧(f，)上车辆的载货能力；心，其它节点为客户；4．模型目标函数及约束条件可以表述如下：{1．，胛'：客户节点集合；z。=∑∑《+∑∑c⋯kEKjEV’∈

6、f．jEV⋯={(f，}：f，J∈v,i≠：弧集合；f≠J基金项目：国家自然科学基金(71071035)。作者简介：赵璐，上海交通大学管理科学与工程硕士研究生，研究方向：城市物流；赵磊，上海交通大学管理科学与工程博士研究生，研究方向：车辆路径优化，物流与供应链管理；朱道立，博士、教授，研究方向为管理决策，物流与供应链。38上淘潸旰惮ShanghaiManagementScience35卷第5期l2013年10,EJlVOI．35lNo．5IOctober．2013e，∑∑k：1节点，则用整数1—9表示9个客户

7、，用0表示起始点。EKieV如果得到结果为01702304560980，则该问题的路∈，∈，∑k一∑k=0径解决方案为4条路线，即4辆车分别对客户节点1和7，2和3，4、5和6，9和8按照顺序服务。∈，∑一∑Yj=9f∈f∈圃Vf，_，∈V,i≠，∑k≤∑-q)计算种群中各条染Vf∈，∈’，k∈K，max(ul+，口kk)色体的适应度二=二二二+k≤q_(k)对种群中的每个染色体进行遗传操作Vf∈，+ai≤∑∑口lkk(选择、交叉、变异)(7)J∈keKl二j[二=_生成子代种群lVi，∈，i≠，k∈，k∈{

8、0，1)(8)蔷否r(一)≤～(9)l∈(IlL(J，((((10)E)2)3)45))6薷的染径色解体决辫对方应案的尘路l—叫—结—束式(1)描述该模型的目标函数，即配送成本，图1遗传算法结构图包括配送车辆的固定成本和与行驶路程和车型相关的可变成本。式(2—10)为约束条件：式(2—3)2．3初始种群生成表示每个客户被一辆车服务且仅被服务一次；式本文设定种群规模为100。随机生成100组客(4)表