物流配送优化问题及算法

1、旅行商问题traveling salesman problem tsp: 这个问题字面上的理解是有一个推销员要到n个城市推销商品他要找出一个包含所有n个城市的具有最短路程的环路。tsp的历史很久最早的描述是1759年欧拉研究的骑士周游问题即对于国际象棋棋盘中的64个方格走访64个方格一次且仅一次并且最终返回到起始点。tsp由美国rand公司于1948年引入该公司的声誉以及线性规划这一新方法的出现使得tsp成为一个知名且流行的问题。 2、中国邮递员问题chinese postman problem cpp: 同样的问题在中国还有另一个描述方法一个邮递员从邮局出发到所辖街道投递邮件最后返回邮局如果他必须走遍所辖的每条街道至少一次那么他应如何选择投递路线使所走的路程最短这个描述之所以称为中国邮递员问题 因为是我国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。 3、“一笔画”问题drawing by one line: 还有一个用图论语言的描述方式平面上有n个点用最短的线将全部的点连起来。称为“一笔画”问题。 4、配送路线问题route of distribution: tsp问题在物流中的描述是对应一个物流配送公司欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。tsp问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间搜索空间是n个点的所有排列的集合大小为n-1。可以形象地把解空间看成是一个无穷大的丘陵地带各山峰或山谷的高度即是问题的极值。求解tsp则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 5、多回路运输问题vehicle routing problem vrp: 多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线使车辆有序地通过它们在满足一定的约束条件下如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等达到一定的优化目标如里程最短、费用最少、时间最短车队规模最少、车辆利用率高。vrp问题和tsp问题的区别在于客户群体的数量大只有一辆车或一条路径满足不了客户的需求必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于tsp问题vrp问题更复杂求解更困难但也更接近实际情况。 6、多个旅行商问题multiple tsp: 由于限制条件的增加tsp问题可以衍生出多个旅行商问题mtsp就是一个出发点m个旅行商的tsp即所访问的客户没有需求车辆没有装载的限制优化目标就是要遍历所有的客户达到总里程最短 7、最近邻点法nearest neighbor: 这是一种用于解决tsp问题的启发式算法。方法简单但得到的解并不十分理想可以作为进一步优化的初始解。求解的过程一共四步首先从零点开始作为整个回路的起点然后找到离刚刚加入到回路的上一节点最近的一个节点并将其加入到回路中。重复上一步直到所有的节点都加入到回路中最后将最后一个加入的节点和起点连接起来构成了一个tsp问题的解。 8、最近插入法nearest insertion: 最近插入法是另一个tsp问题的求解方法。它的求解过程也是4步首先从一个节点出发找到一个最近的节点形成一个往返式子回路在剩下的节点中寻找一个离子回路中某一节点最近的节点再在子回路中找到一个弧使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小实际上就是把新找到的节点加入子回路以后使得增加的路程最短就把这个节点增加到子回路中。重复以上过程直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂但可以得到相对比较满意的解。 9、节约里程法saving algorithm: 节约算法是用来解决运输车辆数目不确定的vrp问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路每次使合并后的总运输距离减小得幅度最大直到达到一辆车的装载限制时再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。 10、扫描算法sweep algorithm: 它也是求解车辆数目不限制的vrp问题的启发式算法。求解过程同样是4步以起始点为原点建立极坐标系然后从最小角度的两个客户开始建立一个组按逆时针方向将客户逐个加入到组中直到客户的需求总量超出了车辆的载重定额。然后建立一个新的组继续该过程直到将全部客户都加入到组中。