摘 要

Abstract IV

1 绪论 1

1.1 课题研究背景 1

1.2 本文研究的目的及意义 2

1.2.1 研究目的 2

1.2.2 研究意义 2

1.3 国内外研究现状 2

1.3.1 国外研究现状 2

1.3.2 国内研究现状 3

1.3.3 可进一步深入研究的问题 4

1.4 本文研究的对象 4

1.5 研究思路与技术方案 4

1.6 本文的研究内容和基本结构 4

2 车辆路径问题的相关理论知识分析 5

2.1 车辆路径问题的相关概念 5

2.2 车辆路径问题的要素特征 6

2.3 车辆路径问题的目标 6

3 车辆路径指派问题的模型 7

3.1 一般情况下的车辆路径指派模型 7

3.1.1 模型假设 7

3.1.2 符号变量说明 7

3.1.3 模型建立 7

3.2 允许空车调度的车辆路径指派模型 8

3.2.1 模型假设 8

3.2.2 符号变量说明 9

3.2.3 算法设计 9

3.2.4 模型建立 10

4 模型验证和结果分析 12

4.1 引言 12

4.2 问题描述 12

4.3 问题求解 13

4.4 结果分析 14

5 总结与展望 15

5.1 本文的主要结论 15

5.2 经济性和适用性分析 15

5.3 未来的研究展望 15

参考文献 17

致 谢 19

附 录 20

摘 要

大部分物流企业都有降低运输成本的迫切需求，但由于缺乏有效的运输管理，在实际的运营中往往无法使资源的利用率达到最大化。企业运输组织优化的核心问题可归结为车辆路径问题。

本文从简单的公路运输系统出发，研究了单个物流企业的多车型、有服务时间要求的车辆路径指派问题模型，然后加入空车调度的因素使模型更加完善。在查阅了国内外关于车辆路径问题的相关研究文献后，本人选取了一个典型的车辆路径问题对模型进行验证，然后对求解结果进行汇总和分析。

根据模型验证的结果，本研究得到以下主要结论：VRP模型的应用能有效提高物流运输系统的决策效率，允许空车调度可为企业提供更优质的车辆路径优化方案。

关键词：车辆路径问题；空车调度；车辆调度计划

Abstract

Most logistics enterprises have an urgent need to reduce transport costs, but due to the lack of effective transport management, in the actual operation often cannot maximize the utilization of resources to optimize.The core problem of enterprise transport organization can be reduced to the problem of vehicle routing.

Based on simple highway transportation system, this paper studies the models with a single logistics enterprise service time model of vehicle routing assignment problem, and then add in the element of deadhead scheduling so as to further perfect model. After reading the domestic and foreign research literature on vehicle routing problem,I selects a typical vehicle routing problem to verify this model, and then summaries and analyzes the solving result.

According to the results of model verification, the main conclusions of this study are as follows: the application of VRP model can effectively improve the decision-making efficiency of logistics transportation system, allowing vehicle deadhead scheduling can provide enterprises with better vehicle routing optimization scheme.

Key Words：vehicle routing problem; deadhead scheduling; vehicle scheduling

1 绪论

1.1 课题研究背景

随着社会经济环境的快速发展，现代物流业成为国民经济的重要组成部分。在优化社会资源配置、调整产业链结构、提高国民经济总体运行效益等方面，现代物流业都发挥着重要的作用。新世纪以来我国物流产业快速发展，2018年我国物流总费用达13.3万亿元，占GDP比重为14.8%。该比重虽已连续多年下降，但对比发达国家（如美国、日本、德国等）均未到10%，我国物流产业仍有较大发展空间。为进一步提高物流行业运行效率、减少无用的物流成本消耗，我国近年来大力推动物流供给侧改革，目前已初见成效，我国物流行业正处于持续发展的繁荣状态^[1]。

为满足社会经济对物流业逐渐增长的巨大需求，现代物流业的运营模式已逐步从传统的运输与仓储业务转变为全面的供应链管理业务，我国许多企业正逐步发展为可提供多样化服务的综合性物流企业。但对于大部分物流企业而言，尤其是中小型第三方物流企业，以道路运输为主的运输业务仍是核心业务。显而易见，运输费用占物流总费用的比重最大，是影响物流总成本的关键要素。因此，如何提高运输业务的效率、降低运输成本成为学术界和企业界人士关注的重点问题之一。

大部分物流企业都有降低运输成本的迫切需求，但由于缺乏有效的运输管理，在实际的运营中往往无法使资源的利用率达到最大化。在道路运输中车辆是运输的主体，车辆管理在运输管理中处于十分重要的地位。由于一些不合理的车辆管理，导致运输车队调度混乱、装载率低等情况的出现，极大地浪费了企业的运输资源。从企业运输环节的整体出发，统一调度车辆，合理规划行驶路线，是降低运输总成本、提高运营效率的关键。

企业运输组织优化的核心问题可归结为车辆路径问题（vehicle routing problem，VRP），自1959年Dantzing和Ramser首次提出VRP以来，VRP及相关研究受到了广泛的关注，直至今日VRP仍是现代物流领域研究中的热点难题^[2]。为满足企业实际的需求，VRP研究中模型的构筑往往会较为复杂。