1. 研究目的与意义、国内外研究现状（文献综述）
课题意义：伴随时代进步，公共交通、快递行业蓬勃发展，快递的配货、入库、分拣、出库环节都影响着送货的时效性，此外，递员送货的效率也格外重要。快递员通过在分拣中心采集某一片区的包裹后，如何高效并选择最佳路径送货上门，成为了降低快递员工作压力，提高快递员送货效率的关键。
应用前景：配送成本占物流的各项成本的比例相当高，配送路线的合理与否影响到成本与效益，特别是多用户、小范围内多点配送路线的确定更是一项复杂的设计问题。对于当代企业。如何恰当选取和优化配送路线更是一项可以很大程度提高企业效益的事情，同时对于配送过程中的交通堵塞和路面同行效率的判定也极为重要。取好的路线不仅可以提高企业效益，也可减轻城市交通负担。本文也基于此针对快递配送优化问题展开研究。
国内研究进展：国内诸多学者对最短路径的研究在各领域都进行了运用与发展。如：王树西,吴政学[1]（2012）的算法实验表明,改进的标号法能够有效解决交通路线的设计问题，并在此基础上,开发了"北京市道路最优路线选择系统",以提供起点和终点之间的最优路线,帮助用户选择出行路线；王海梅[2]（2008）的研究重点研究了作战背景下满足一定解算条件的最优路径问题,最短路径的高效算法,多约束最优路径问题以及时变网络最优路径问题；朱霁平,苟永华[3]（2002）针对城市火灾扑救中的资源调度问题 ,综合考虑道路交通的各种迟滞因素 ,对通用的dijkstra法进行修正。通过对两种方法计算结果对比表明 ,修正算法更为合理。王元彪[4]（2007）针对智能交通系统,研究最佳路径和最短路径的计算,由于越来越多的实时信息参与计算,使得计算行车时间最短的路径变得更频繁,通过建立相关的数据索引表,可以高效地实现dijkstra算法,与原始算法相比,大大提高了效率；朱学智（2015）提出了一个带有四个局部路径替换策略的解决动态最短路径问题的遗传算法[5]。这些局部路径替换策略是由dijkstra的最短路径算法所启发,并且在环境发生改变的时候进行调用来产生一些局部最短路径树。并且在种群进化时,这些保存的局部最短路径树用来增强个体的性能。
2. 研究的基本内容和问题
研究的目标、内容：旨在一个有向的非负权稀疏图中，给定规定的起点，必经节点和任意终点。目标是寻找一条从起点出发，不必按照所给顺序，经过所有必经节点，到达终点的最佳路径。在这条最佳路径中，可能会经过交通网络中除起点、终点和必经节点以外的自由节点。（其中：必经节点——最佳路径中必须包含的节点；关键节点——起点、终点和必经节点统称关键节点；自由节点——除关键节点以外的其他节点。）
拟解决的关键问题：将庞大的稀疏图，分解成两个易于求解的子问题，然后再全局求解最短路径。因此，对所求的交通网络稀疏图必经节点的最佳路径问题，可以分解为两个过程1)求解关键节点间的最佳路径，将庞大的有向非负权稀疏图简化为关键节点间的稠密图 (关键节点到关键节点的路径上的自由节点隐藏);2）在关键节点间的稠密图中，寻找一条从起点出发经过所有必经节点到达终点的最佳路径。
3. 研究的方法与方案
在研究最佳路径的问题上，有许多优越的算法涌现，其中在正权值的算法中，最为著名的有dijkstra算法（常用于解决单源最短路径问题）、floyd算法（用于解决多源最短路径问题），但是这两种算法都只能解决两点之间的路径问题，无法解决多点联通的最短路径，现阶段少有文献触及这一方面的研究。下面介绍若干种最短路径的算法，综合多种方法使得研究具有一定可行性。
1传统dijkstra算法
dijkstra算法是1959年由荷兰计算机科学家dijkstra提出的图论中求最短路径的常用算法,该算法可求得图中一点到其他任一顶点的最短路径.dijkstra算法将网络节点分成3部分未标记节点、临时标记节点和永久标记节点.在网络图中,将所有节点初始化为未标记节点,在搜索过程中游历节点和任一路径中相连通的节点为临时标记节点,每次循环都是把从临时标记节点中搜索距起源点路径长度最短的节点作为永久标记节点,直至找到目标节点或者所有的节点都成为永久标记节点后才算法结束.如图1所示,假设节点网络的起源点为节点0,目标点为节点4,求节点0到节点4最短路径的距离(各节点间的长度是假设的).
4. 研究创新点
通过文献的查找及翻阅，可知对于N点图，网上绝大多数学者研究的都是两点之间最短路径的设计问题，对于N点图中必须经过若干点的最短路径问题涉及较少，包括目前高德、百度等国内主流导航软件也聚焦于两点之间最短路径，并未对多点最短联通路径进行规划（目前导航软件只可依次设置若干地点，依次通过，并未实现多点打乱选定顺序进行路径规划）。因此多点最短路径的规划问题，是我需要查阅资料和研究的方向。
5. 研究计划与进展
预计三月上旬完成改进算法的推导和演算工作；
三月中下旬录入小范围交通地图进行编程和实验工作；
四月完成实验方法的优化及论文的撰写工作。
