物流配送重要.ppt

1、1,连锁商业货物配送中的车辆优化调度模式研究与开发（国家95攻关项目，1999-2001）,北京清华大学数学科学系,实际案例介绍,2,连锁商业货物配送中的车辆优化调度模式研究与开发,一、研究背景,二、优化问题数学模型,三、解决的理论与方法,四、软件成果,3,一、研究背景,1、香港某连锁店配送（1997年）,分 店：240 (香港岛，九龙半岛，新界，其他) 运输车辆：64（6个车型：封闭、敞棚、低开等； 各种吨位）,2、北京某超市连锁店（2000年）,分 店：20余家（力求3-5年时间建成50-100家） 配送中心：五环外某处 运输车辆：9（车型：大货5吨、2.75吨； 小货2吨、1.75吨；

2、北旅1吨）,4,连锁店配送示意图,5,一、研究背景,要 求： （1）计算机给出派车单（在线，离线），提供车辆装货的方案和车辆行走的路线。 （2）车队的规模大小。,主要考虑因素： （1）多个分店货物的混装； （2）分店装卸时间窗口、车型的限制； （3）道路时间窗口、吨位的限制； （4）司机的工作时间限制，负荷均衡； （5）车辆平衡负载； 等等,6,二、优化问题数学模型,2. 车辆路线问题(vehicle routing) 车辆行驶路线最短,1. 装箱问题(bin packing) 多个分店货物混装问题，需求超出车载的分店装车问题,3. 匹配问题(allocation) 车辆总数，车型搭配，司机人

3、数,4.平衡问题(balancing) 司机的工作时间，车辆的行驶里程,7,二、优化问题数学模型,6. 其他 打折，赠送,5. 时间窗口问题(time-window) 供货时间、道路限制,各种复杂模型(NP-Complete)的综合集成 多目标优化；连续/离散优化；线性/非线性优化,以上问题必须考虑：道路限制、供货时间限制、车载量限制和配送中心调度员的调度时间周期,8,三、解决的理论与方法,分解、协调优化；启发式、满意解 近似算法、贪婪方法等； 现代优化、智能算法等（如tabu search, simulated annealing, evolutionary algorithms, neur

4、al networks etc. ),2. 路线问题(routing) 扇形法 、中心扩散等,1.装箱问题(bin packing) NF，WF，BF等,9,三、解决的理论与方法,扇形法,10,三、解决的理论与方法,中心扩散,11,主算法,Step1(全局计算)若不是特殊店，按区计算未预装且满足车载限制的店“是否一定送货”和“店级别”的加权和，从最大车辆开始，将车辆分配给最大权和的区域，直至全部需求店预装或全部车辆派完。 （车辆数循环）,Step2（区域计算）在每一个区域内，根据现有的店和分配车辆，,2.1 根据车辆数目并以始终点相同分别采用“insertion”算法，给出每车的预装方案； 2

5、.2 若“一定送货”店或“低”级别店得到送货而“高”级别店没有送货，此时，根据“是否一定送货”，“店级别”字典序排列店顺序，按道路连通情况修正预装方案； 2.3 以每车可开始工作的最早时间分别计算每店的供货时间表。输出各车辆的装车方案和各车辆可以再工作的开始时间。,12,主算法,Step3 （全局计算）判别是否有未服务的店且车辆开始服务时间是否满足再装车要求。若有未服务的店且车辆满足再装车要求，则返回Step1. Step4 特殊店处理。选载重最匹配车辆。 Step5（全局计算）司机分配优化。按车辆的最后一次预装方案的一个店同司机家最近分配车辆。 Step6 （区域计算）将司机家作为一个店加入，以配货中心为起点，司机家为终点，采用“insertion”算法再次优化计算每一车辆的最后一次预装店路径优化及计算每一店的送货时间表。 Step7 （全局计算）调整时间表。对每一个车辆的开始和结束时间，尽量将最佳时间段调给A级店。 Step8 输出。,13,