辽宁工业大学
毕业设计（论文）
开题报告
题目基于Dijkstra算法的物流配送路径研究
汽车与交通工程学院（系）物流工程专业091 班
学生姓名黄仕勇
学号091204013
指导教师王冬梅
开题日期：2013年3月22日
一.毕业设计题目的来源、理论或实际应用意义
1、来源：生产实践
2、理论或实际应用意义
配送运输是物流系统中最重要的组成部分之一，正是通过配送运输，配送中心才得以最终完成货物从生产商到用户的转移。
由于配送中心每次配送活动一般都面对多个非固定用户，并且这些用户坐落地点各不相同，所以对于它们的配送时间和配送数量也都不尽相同。
如果配送中心不进行运输路线的合理规划，往往会出现不合理运输现象，不仅造成运输成本上升，而且导致配送服务水平难以提高，因此经常对配送路线进行规划调整是大多数配送中心的一项重要工作。
然而在配送运输路线规划上，基本问题就是求最优路线，最优路线的核心算法就是最短路径算法。
最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而将Dijkstra作为研究对象对流配送运输路线规划有重要的实际意义。
二.题目主要内容及预期达到的目标
1、主要内容
本研究主要是使用Dijkstra算法对配送路径进行设计，并在此基础上对Dijkstra算法进行进一步改进，使其达到最好的优化效果。
具体内容及结构如下：
第一章绪论
1.1选题背景和意义
1.2国内外研究现状
1.2.1国内研究现状
1.2.2国外研究现状
1.3研究内容及目标
第二章配送基本理论
2.1配送与物流
2.2配送运输
开题报告要点：1、毕业设计（论文）题目的来源，理论或实际应用意义。
2、题目主要内容及预期达到的目标。
3、拟采用哪些方法及手段。
4、完成题目所需要的实验或实习条件。
5、完成题目的工作计划等。
（开题报告不够用时可另附同格式A4纸）
1
2.2.1配送运输的概念
2.2.2影响配送运输的因素
2.2.3配送运输基本作业流程
2.3配送线路
2.3.1配送线路选择问题的结构
2.3.2配送线路的类型
2.3.3配送线路的优化原则
第三章物流配送中VRP模型及基本算法
3.1 VRP的提出
3.2物流配送中VRP的数学模型
3.2.1VRP的描述
3.2.2VRP的数学模型
3.3VRP的基本算法
第四章Dijkstra算法在VRP中的应用
4.1 Dijkstra算法
4.2 Dijkstra的实例分析
4.3原始Dijkstra算法的不足
4.4Dijkstra算法的改进
4.4.1数据储存的改进
4.4.2算法执行效率的改进
4.4.3数据结构的改进
4.5 改进实现
第五章结论与展望
5.1结论
5.2展望
2、预期达到的目标
（1）通过对Dijkstra算法的研究，对配送路径进行优化，并实现系统编程运行。
（2）结合案例，实施操作，建立优化网络配送路径图。
2
（3）对Dijkstra算法进行优化，使其更适应实际操作。
三．拟采用哪些方法和手段
迪科斯彻算法（Dijkstra's algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger Wybe Dijkstra）发明的。
算法解决的是有向图中单个源点到其他顶点的最短路径问题。
其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。
当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。
就其方法的稳定性，准确性以及一系列的优越性，常被运用到配送线路优化的问题上。
四．完成题目所需要的实验和实习条件
研究所需条件：纸张、打印设备、图书馆、互联网上获取国内外文献资料。
根据论文的写作需要，实习单位为锦州市亿家人服装批发城。
亿家人服装批发城是一家大型服装连锁超市在东北三省、河南、河北、山西有上千家连锁店。
主要经营服装，针织，童鞋，箱包等商品，对外有很强大的供销网络系统，适于实习研究。
五．完成题目的工作计划
2月27日～3月3日：文献检索，选定毕业设计题目
3月4日～3月10日：翻译外文检索、调研、实习
3月11日～3月17日：确定文章总体框架、结构
3月18日～3月24日：填写开题报告、准备开题答辩
3月25日～3月31日：研究我国物流配送路径管理的现状和特点
4月1日～4月7日：学习MATLAB软件
4月8日～4月14日：学习物流配送、车辆路径问题、Dijkstra算法等基本理论
4月15日～4月21日：建立物流配送路线模型，即VRP模型
4月22日～4月28日：使用Dijkstra算法对VRP模型进行求解
4月29日～5月5日：发现Dijkstra求解VRP模型的局限
5月6日～5月12日：填写中期检查报告、准备中期检查
5月13日～5月19日：Dijkstra算法的数据存储、计算执行效率等改进
5月20日～5月26日：改进结果评价、完成论文初稿
5月27日～6月2日：完善论文初稿
6月3日～6月9日：完成论文终稿
6月10日～6月16日：完善论文终稿
6月17日～6月23日：打印、装订论文，准备毕业答辩
3
查阅资料、文献目录
[1] 曾华. 真实道路下大规模车辆路径问题算法研究与应用[D].山东大学，2007.
[2] 晏梦君. 遗传算法在配送线路优化系统中的应用[D]. 吉林大学，2007.
[3] 牟燕妮. 物流配送中路径优化的选择研究[D]. 沈阳工业大学，2006.
[4] 尚艳华. 物流配送中车辆路径问题研究[D].武汉理工大学，2005.
[5] 雷同飞，张宏. 物流配送中的车辆路径优化问题[J]. 市场现代化，2009，1：119-120.
[6] 高鹏，徐瑞华. 物流配送线路优化的改进遗传算法研究[R]. 同济大学，2003.
[7] 韩世莲. 物流配送线路多目标优化方法研究[D]. 东南大学，2005.
[8] 许星. 物流配送路径优化问题的研究[D]. 浙江大学，2006.
[9] 刘峰. 物流配送路径优化算法的研究与应用[D]. 吉林大学，2007.
[10] 郑斌. 区域物流网络中心选址及线路优化研究[D]. 大连海事大学，2011.
[11] Liu Li. Overal optimization of distribution network, Int.D. 2001.
[12] 汤杰. 基于蚁群算法的物流配送模型研究[D]. 重庆理工大学，2009.
[13] 盖衫. 基于遗传算法的物流配送调度系统[D]. 长春理工大学，2006.
[14] 张颖敏. 基于节约里程法的物流配送线路优化与改进研究[J]. 物流科技，2010.
[15] 汪利军. 基于改进遗传算法的城市配送车辆调度优化研究[D]，长沙理工大学，2007.
[16] 陈志伟．基于GIS的配送线路优化的研究与设计[D]. 浙江工商大学，2009.
4
指导教师意见：
(对本课题的深度、广度及工作量的意见和对设计结果的预测)
指导教师签字：
年月日教研室意见：
教研室主任签字：
年月日
5
开题报告要点：1、毕业设计（论文）题目的来源，理论或实际应用意义。
2、题目主要内容及预期达到的目标。
3、拟采用哪些方法及手段。
4、完成题目所需要的实验或实习条件。
5、完成题目的工作计划等。
（开题报告不够用时可另附同格式A4纸）。