摘要：配送在物流系统中扮演着重要的角色，是物流顺利实施的根本保障。在信息技术高速发展的今天，设计高效实用的物流配送算法为物流配送系统实现合理路径运输,从而节约运输时间、减少运输费用, 提高现代物流系统效率和降低成本非常必要。本课题借鉴已有的数学模型，建立城市配送中心两点间的多目标最优路径问题模型，并在此基础上借助运筹学路网中的最短路径算法和前k条简单路径的算法对此模型给出三种算法。课题最后选择一种较为理想的算法利用C++语言编写了程序，在Dev C++编译器上进行了编译和调试后，程序在三个目标权值下成功地给出了九条路径，并把这九条路径的各个目标权值列成表格以备分析。程序给出了较为理想的结果。

关键词：物流  最优路径   多目标最优路径  前K条最短路径  简单路径

一：课题的意义：

物流作为一种经济活动，随着商品经济发展而形成。在经济日益全球化的今天，现代物流作为“第三个利润源泉”正受到日益广泛的重视，并面临着前所未有的发展机遇。现代物流已经贯穿于我国生产、分配、流通和消费的各个领域，社会对物流需求的数量、质量正在不断提高，这些都为我国物流与国际物流接轨并融入全球物流一体化提供了条件。

物流配送在物流系统中扮演着重要的角色，是物流顺利实施的根本保障，畅通、高效的物流不但可以提高货物周转效率，还能通过规模优势有效降低物流成本、减少企业库存，从而提高企业经济效益。

物流信息是物流管理的基础，计算机技术的应用加速了信息的获取，缩短了物流的活动周期。设计高效实用的物流配送算法、应用高速发展的计算机系统为物流配送系统实现合理路径运输,从而节约运输时间、减少运输费用, 提高现代物流系统效率和降低成本非常必要。

本课题通过深入学习现有的模型算法，借鉴已有的数学模型，并根据城市配送中心的实际需求，建立城市配送中心两点间的多目标最优路径问题模型，并在建模的基础上，借助运筹学路网中的最短路径算法和前k条简单路径的算法对模型求解，帮助用户找到满足自己需要的最优路径。

二: 最优路径问题研究现状

最优路径问题是人们长期研究的问题，在物流配送和选址、城市交通、车辆导航系统以及GIS领域等方面有广泛的应用。

配送的目标之一就是以最小的代价，将产品从原产地（或物流配送中心）转移到规定地点。因此，制定车辆调配计划和配送路线计划就显得非常重要了。一般说来，最小的代价所对应的配送路径就是最优路径。

最优路径绝不等同于最短路径。在物流配送过程中，最短路径，无论是时间最短还是距离最短，都不一定是行车意义上的最优。最优路径需要考虑许多因素：有的用户关注运输距离，有的用户关注送货时间，而道路通行状况（道路是否平坦、有没有时间窗、交通状况等）^[2]也是每个用户必须考虑的。由此可见不同用户对配送的要求不可能完全相同，因而他们对最优的理解也不尽相同。

以往有关最优径算法的研究大部分集中在最短路径上，而不一定是用户需求意义下的“最优”路径。主要是因为最短路径相对于最优路径，人们研究得较早，容易建立数学模型，模型相对简单，算法也比较成熟。最短路径是最优路径的基础，大多数最优路径都是通过解决最短路径来实现的。

最短路径的算法比较成熟。较为出名的算法有Dijkstra算法、逐次逼近算法和floyd算法等等。其中Dijkstra算法是公认的解决网络中两点间最短路径的最好算法。

从Dijkstra算法诞生到现在，人们对他进行了很多的改进^[3]，以适应越来越庞大的网络体系。改进主要表现在两个方面^[4]：

在对临时标号点的排序问题上选取堆排序，大大降低了数据比较的频率。堆排序的主要运行时间消耗在建初始堆上,而对于Dijkstra 算法来说,整个最短路径的搜索过程中进行的n次堆排序只需要建一个堆，从而明显克服了堆排序的主要缺点，使堆排序的优势更加明显地发挥出来。