连锁商业货物配送中的车辆优化调度模式研究及开发

1、1连锁商业货物配送中的连锁商业货物配送中的车辆优化调度模式研究与开发车辆优化调度模式研究与开发2连锁商业货物配送中的连锁商业货物配送中的车辆优化调度模式研究与开发车辆优化调度模式研究与开发一、一、研究背景研究背景二、优化问题数学模型二、优化问题数学模型三、三、解决的理论与方法解决的理论与方法四、四、软件成果软件成果3一、一、研究背景研究背景1、香港某连锁店配送（、香港某连锁店配送（1997年）年）分 店：240 (香港岛，九龙半岛，新界，其他)运输车辆：64（6个车型：封闭、敞棚、低开等； 各种吨位）2、北京、北京某超市连锁店某超市连锁店（2000年）年）分 店：20余家（力求3-5年时间建成

2、50-100家）配送中心：五环外某处 运输车辆：9（车型：大货5吨、2.75吨； 小货2吨、1.75吨； 北旅1吨）4 配 货 中 心ABDCFEHGI车库连锁店配送示意图连锁店配送示意图5一、一、研究背景研究背景要 求：（1）计算机给出派车单（在线，离线），提供车辆装货的方案和车辆行走的路线。（2）车队的规模大小。主要考虑因素：（1）多个分店货物的混装；（2）分店装卸时间窗口、车型的限制；（3）道路时间窗口、吨位的限制；（4）司机的工作时间限制，负荷均衡；（5）车辆平衡负载；等等6二、优化问题数学模型二、优化问题数学模型 2. 车辆路线问题车辆路线问题(vehicle routing)车辆行

3、驶路线最短车辆行驶路线最短 1. 装箱问题装箱问题(bin packing)多个分店货物混装问题，需求超出车载的多个分店货物混装问题，需求超出车载的分店装车问题分店装车问题 3. 匹配问题匹配问题(allocation)车辆总数，车型搭配，司机人数车辆总数，车型搭配，司机人数 4. 平衡问题平衡问题(balancing)司机的工作时间，车辆的行驶里程司机的工作时间，车辆的行驶里程7二、优化问题数学模型二、优化问题数学模型 6. 其他其他打折，赠送打折，赠送 5. 时间窗口问题时间窗口问题(time-window)供货时间、道路限制供货时间、道路限制各种复杂模型各种复杂模型(NP-Complet

4、e)的综合集成的综合集成v多目标优化；连续/离散优化；线性/非线性优化以上问题必须考虑：道路限制、供货时间限以上问题必须考虑：道路限制、供货时间限制、车载量限制和配送中心调度员的调度时制、车载量限制和配送中心调度员的调度时间周期间周期8三、三、解决的理论与方法解决的理论与方法分解、协调优化；启发式、满意解近似算法、贪婪方法等；近似算法、贪婪方法等；现代优化、智能算法等（如现代优化、智能算法等（如tabu search, simulated annealing, evolutionary algorithms, neural networks etc. )2. 路线问题路线问题(routing)

5、 v扇形法扇形法 、中心扩散等中心扩散等1. 装箱问题装箱问题(bin packing)vNF，WF，BF等等 9三、三、解决的理论与方法解决的理论与方法扇形法扇形法配 货中 心ABDCFEHGI车库10三、三、解决的理论与方法解决的理论与方法中心扩散中心扩散 配 货中 心ABDCFEHGI车库11主算法主算法 Step1(全局计算)若不是特殊店，按区计算未预装且满足车载限制的店“是否一定送货”和“店级别”的加权和，从最大车辆开始，将车辆分配给最大权和的区域，直至全部需求店预装或全部车辆派完。 （车辆数循环） Step2（区域计算）在每一个区域内，根据现有的店和分配车辆，q 2.1 根据车辆数

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