二、多个起点和多个终点的路径规划问题
多个起点和终点的路径优化，需要确定各供求地点之 间的最佳供应关系。运用线性规划,数学模型可以描述为：
有m个产地 Ai，i =1，2，…，m，可供应量分别为ai， i=1，2，…，m；有n个销地 Bj，j=1，2，…，n，需要量 分别为bj，j=1，2，…，n；产销平衡，从Ai到Bj 运输单位 货物的运价（也可以是时间或距离）为cij。问如何调运这 些货物，使得运费（或时间、吨公里数）最少？ 常见的解决方法有：
1、单纯形法 2、图表分析法 3、图上作业法 4、表上作业法 5、供求不平衡运输模型 三、起点和终点相同的路径规划
起点和终点相同的路径规划问题是物流配送业务中的常见问题。 由于要求车辆必须返回起点，问题的难度提高了。 由于要求车辆必须返回起点，问题的难度提高了。解决这类 问题的目标是找出途中经过的点的顺序，使运输工具依次经过 问题的目标是找出途
6 / 13
中经过的点的顺序，使运输工具依次经过 所有送货点并满足各点对送货时间的要求 并满足各点对送货时间的要求， 所有送货点并满足各点对送货时间的要求，且总出行时间或总 距离最短。 旅行推销员（ NP难题 距离最短。——“旅行推销员（TSP）”问题，属于NP难题。 旅行推销员 TSP） 问题，属于NP难题。 随着问题中包含节点个数和约束条件的增加， 随着问题中包含节点个数和约束条件的增加，求解问题的复 杂程度增加，要找到最优路径非常困难。 杂程度增加，要找到最优路径非常困难。即使用最快的计算机 进行计算，求最优解的时间也非常长。 进行计算，求最优解的时间也非常长。启发式求解法是求解这 类问题的好方法。 类问题的好方法。 见p206页例题3
运输批量越大，运输费率越低。
将小批量货物合并成大批量货物进行运 输是降低运输成本的主要方法。 输是降低运输成本的主要方法。 （三）合理路线和时间安排的原则
7 / 13
原则１将相互接近的停留点的货物装在一辆车上运送，以 便使停留点之间的运行距离最小化。
（a）差的串联 （b）更好的串联
原则2：将集聚在一起的停留点安排同一天送货，要避免 不是同一天送货的停留点在运行线路上重叠。
原则3： 合理的运输路线 一辆运货车顺次途经各停车点的路线要呈凸状，或泪 点的路线要呈凸状， 一辆运货车顺次途经各 点的路线要呈凸状 滴形，各条线路之间是不交叉。
8 / 13
相关推荐：
loading