基于混合策略的动态物流车辆派送路径问题的研究

摘要

随着社会经济的高速发展，电子商务的迅速发展、连锁店模式的兴起以及商业流程缩短等因素，物流配送的地位越来越重要。各大物流公司为了提升竞争力，满足顾客需求，都在大力推进物流配送的信息化、智能化。另一方面，随着私人汽车数量的急剧增加，城市交通拥堵情况日益严重，给物流配送的实时性增加了不少难度。因此，利用先进的信息技术获取道路交通信息去安排物流车辆的配送，选择最优路径以达到最佳的配送效率，节省配送成本，对物流企业是至关重要的。
　　针对物流配送的特点，并结合交通路网的相关理论知识，建立了动态车辆配送模型。本文结合真实的复杂路网配送环境，提出了一种混合策略算法以求解建立的模型。该算法主要分为两个部分，初始配送顺序的安排和最短路径的搜索。首先，本文引入曼哈顿距离，利用遗传算法进行初始配送顺序的安排，并通过实验证明了其有效性并且极大优化了算法运行时间。接着，通过采用floyd算法和dijkstra算法结合的混合策略，并提出路网关键点，在路网关键点更新交通信息并计算路网中两个关键点的路径，有效优化了算法执行时间并且合理避开拥堵，并且在获取不到路网实时信息的情况下也能快速求解。
　　最后，本文以北京市的真实交通路网为基础并考虑早晚高峰时段交通情况建立了58个顾客配送点的算例，通过算例的实验结果分析，证明了本文所提出的算法在真实的交通路网条件下能有较快的算法执行时间并且能合理避开拥堵，具有现实意义。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 本文的主要工作

1．4 本文结构

第2章 相关理论以及问题概述

2．1 VRP关键要素

2．2 VRP分类

2．2．1 按任务特征分类

2．2．2 按车辆载货状况划分

2．3 车辆导航系统

2．3．1 智能交通系统概述

2．3．2 车辆导航系统概述

2．4 路网的表达方法和存储方式

2．4．1 图的定义

2．4．2 路网的基本概念

2．4．3 路网的存储结构

2．5 VRP相关算法

2．5．1 最短路径算法

2．5．2 遗传算法

2．6 本章小结

第3章 VRP模型与混合策略算法

3．1 VRP模型

3．2 初始配送顺序安排

3．2．1 遗传算法解决VRP问题

3．2．2 曼哈顿距离的引入

3．2．3 曼哈顿距离安排配送顺序有效性验证

3．3 相邻顾客点之间最短路径搜索

3．4 实时路线调整

3．5 算法具体步骤

3．6 本章小节

第4章 实验分析

4．1 路网概述

4．2 路网扰动方法

4．3 算例的建立

4．4 实验结果与分析

4．5 基于实时交通信息的物流配送导航软件

4．6 本章小节

结论

参考文献

致谢

附录A 攻读硕士学位期间发表的学术论文目录

附录B 攻读硕士学位期间所参加与的项目