资源描述：
《多车辆配送路线的优化---扫描法教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、多车辆配送路线的优化---扫描法目录1.多车辆配送路线的优化什么是多车辆配送路线的优化模型假设是什么如何求解多车辆配送路线的优化问题2.扫描法何为扫描法求解步骤是什么实例分析1.多车辆配送路线的优化多车辆配送路线的优化t1Part1.1什么是多车辆配送路线的优化经典VRP可描述如下：有多个货物需求点(或称顾客),己知每个需求点的需求量及位置,至多用m辆汽车从配送中心(或中心仓库)送货,每辆汽车载重量一定,安排汽车路线,要求每条路线不超过车辆载重量和每个需求点的需求必须且只能由一辆车来满足,目标是使运距最短或者运输费用最少。例如，一家大型物流中心要为
2、成百上千的客户提供送货或取货的服务，就需要对运输车辆的数量及其行驶路线进行规划以节约成本。多车辆路径问题(VehicleRoutingProblem，VRP)Part1Part1.2模型假设是什么（1）单一物流中心，多部车辆配送。（2）每个需求点由一辆车服务，每个客户点货物需求量不超过车辆的载重容量。（3）车辆为单一车种，即视为相同的载重量，且有容量限制。（4）无时窗限制的配送问题。（5）客户的位置和需求量均为已知。（6）配送的货物视为同一种商品，便于装载。多车辆配送路线的优化Part1Part1.3如何求解多车辆配送路线的优化问题精确优化算法智能
3、优化算法模拟方法启发式方法多车辆配送路线的优化扫描法节约法Part1Part1.3如何求解多车辆配送路线的优化问题多车辆配送路线的优化1、同一车辆服务的客户按距离聚类图1-1合理的车辆分派方案图1-2不合理的车辆分派方案原则Part1Part1.3如何求解多车辆配送路线的优化问题多车辆配送路线的优化2、避免行车路线交叉3．尽可能使用大载重量车辆，减少出车数量4．取货/送货混合安排5．从距仓库最远的站点开始设计线路原则2.扫描法Part1Part2.1何为扫描法扫描法扫描法在VRP求解方法中是一种先分群再寻找最佳路线的算法。求解过程分为两步：第一步是
4、分派车辆服务的站点或客户点；第二步是决定每辆车的行车路线。原理：先以物流中心为原点，将所有需求点的极坐标算出，然后依角度大小以逆时钟或顺时钟方向扫描，若满足车辆装载容量即划分为一群，将所有点扫描完毕后在每个群内部用最短路径算法求出车辆行驶路径。Part1Part2.1何为扫描法扫描法评价扫描法是一种逐次逼近法,用该方法不一定能求得物流配送车辆路径优化问题的最优解,但是能够有效地求得问题的满意解。对于某个具体的物流配送车辆路径优化问题,由于存在多种客户编号方法,当仅选择一种客户编号方案用扫描法求解时,其计算量相对较小,但相应地解的质量可能不会很高;当
5、选用多种客户编号方案用扫描法求解时,一般能得到质量很高的满意解,但相应地,计算量会成倍增加。研究表明,对于物流配送车辆路径优化问题,当每条路线上的客户数目大体相同且配送路线不太多时,用扫描法求解是非常有效的。Part1Part2.2求解步骤是什么扫描法1．以物流中心为原点，将所有客户需求点的极坐标计算出来。2．以零角度为极坐标轴，按顺时针或逆时针方向，依角度大小开始扫描。3．将扫描经过的客户点需求量进行累加，当客户需求总量达到一辆车的载重量限制且不超过载重量极限时，就将这些客户划分为一群，即由同一辆车完成送货服务。接着，按照同样的方法对其余客户划分
6、新的客户群，指派新的车辆。4．重复步骤3，直到所有的客户都被划分到一个群中。5．在每个群内部用TSP算法求出车辆行驶最短路径。扫描法Part1Part2.3实例分析【例2-1】某运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为10吨的货车完成。现在有13家客户有取货要求，各客户的去货量、客户的地理位置坐标见表2-1。已知运输公司仓库的坐标为（19.50，5.56）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。表2-1客户数据信息客户12345678910111213Di(吨)1
7、.92.83.152.4232.252.51.82.151.62.61.5Xi20.018.818.319.118.818.619.519.9320.019.518.719.520.3Yi4.805.175.004.786.425.885.985.935.554.554.555.195.20扫描法Part1Part2.3实例分析第一步建立及坐标【解析】参考表2-1和书上的数据信息，在图2-1上描述出各客户点的坐标位置，并在每个客户编号旁边的方框中标注出该客户的货运量。然后，以仓库为极坐标原点，向右的水平线为零角度线。YX图2-1扫描法Part1Pa
8、rt2.3实例分析第二步扫描划分客户群【解析】以零角度限位起始位置，按逆时针方向进行扫描，将扫描经过的客户需求按照图2-2
