用dijkstra算法实现对整车配送线路的优化

《用dijkstra算法实现对整车配送线路的优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、万方数据第5卷2007盆第5期5月Vof．5MayNo，52007用Dijkstra算法实现对整车配送线路的优化张念摘要：解释了整车配送线路优化的概念，提出了用Dijkstra算法解决该问题的思路，并用实例进行了说明，论证了这种方法的可行性希f实用性。关键词：Dijkstra算法整车配送线路优化中图分类号：TP301．6文献标识码：A文章编号：1006—7973(2007)05—0141—02一、引言在现代物流中，配送环节直接联系商家和消费者，配送瑚：节的好坏直接影响到客户满意度，从而影响企业效益，车辆的优化调度问题是配送中的一个重

2、要课题，它对车辆的利用效率和配送成本有着重要影响。车辆的优化调度问题由Dantzig和Ramser于1959年首次提出，该问题一经提出，茧：即引起了运筹学、图论与网络分析、物流科学、计算机应用等学科专家与运输问题制定和管理者的极大关注，成为运筹学和优化科学研究的前沿和热点问题。车辆优化调度问题是组合优化领域的著名NP难题之一，在计算机等现代信息技术没有出现以前，其求解过程相当困难和复杂，通常需要应用齐H关技术将问题分解或转化为一个或者多个已经研究过的基本问题，如旅行商问题、最短路径问题、最短流问题、最小费用最大流问题、巾国邮递员问题

3、等，再使用比较成熟的理论和方法进行求解，以求得原车辆凋度问题的最优解或满意解。随着计算机技术、人工智能技术、神经网络技术等现代信息技术的不断发展，又出现了许多改进的算法，如Gover在1986年提出的禁忌搜索法、J．Holland教授和他的学生建立发展起来的遗传算法、N．Metropolis提出的模拟退火算法【6l等，这些算法分别适用于不同的情况，在解决不同的优化调度问题中起到了显著作用。本文要讨论的是一种基于Dijkstra算法的优化调度方法，适用于整车配送中的车辆调度问题。二、问题描述整车配送线路优化是本人所作“配送车辆调度系统

4、”项目中的一部分，该项目中涉及到的配送线路规划问题主要有三种：整车配送的线路优化、拼车(合车)的线路优化、多起迄点的线路规划。下面简要说明整车配送问题，所谓整车配送，即一辆车的货物全部从起点到终点。整车配送一般适用于两种情况，一1是货物配送量很大，车辆多次运输时都能满载，此时车辆总是从起点到终点；另一利t情况是配送货物量虽然不大，但是货物比较特殊，不能与其他货物拼装，此时也只能用整车将货物从起点运至终点。对于整车配送线路的优化，就是希望通过一定的方式对配送线路进行规划，使得配送的成本最低。如果撇开其他因素(如不考虑路况)，其实就是要

5、找到从起点到终点的最短距离；如果考虑路况等因素，我们也可以采用加权的方法进行转化，将不同路段的距离乘以相应的权(或系数)，这样同样'可以把问题转化为求最短距离。为了更清楚的描述这个问题，我们取深圳市电子地图的一部分数据，如图1所示，假设现在有一车货物要进行配送，起点是高新超市(图中固)，终点是华侨城(图中国)，如果不考虑其他因素，我们只要能够找到一条连接二者的最短路径，就可以实现车辆的优化调度。7}由?晒{{图1试验用电子地图显然，这类问题可以视为网络规划中的最短路径问题，在求解过程中，我们可以用网络图代表实际的交通运输网络。所谓网

6、络图，就是由点和弧线组成的图，其中，点代表交通网络中的地点，如图1中的囟～鹳；弧线代表点与点之间的连线；弧线旁所标注的数字，表示两点之问的成本(距离、时间或距离和时间的综合指标)。这样，问题就可以转化为求网络图中两个特定点之问的最短路径问题。三、解决方案上面已经提到，这类规划问题可以转化为求网络图中的最短路径问题，故可以考虑采用《数据结构》图论中的理论来进行解决，本项目中就是采用“带权图”的相关方法解决收稿日期：2007—3—26作者简介：张念男(1973一)广州航海高等专科学校计算机与信息工程系高级工程师硕士(510725)研究方

7、向：软件设计方法、信息系统规划、系统分析与系统集成万方数据142中国水运第5卷该问题，采用的是Dijkstra(迪杰斯特拉)算法。1．Dijkstra(迪杰斯特拉)算法简介Dijkstra算法是由荷兰计算机科学家Dijkstra发现的，算法解决的是有向图中最短路径问题。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(U，v)表示从顶点u到v有路径相连：我们以E表示所有边的集合，而边的权重则由权重函数w：E一【0，o。1定

8、义。因此，W(u，v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点问路径的花费值，就是该路径上所有边的花费值总和。已知V中有顶点S及t，Dijkstra算法可以找到S到t的最低花费路径(最