1、 1 摘摘 要要 目前，现代物流产业已经是覆盖整个产业链的、全方位的、立体化的服务供应商， 国家和企业也越来越重视物流在国民经济中的重要地位。现代物流被看作是降低资源消 耗、提高人力素质之后的“第三利润源” 。在物流领域中，车辆行驶路线选择始终是 一个重要的组成部分, 特别是在最近几十年中，许多学者都对其进行了大量的实验和研 究。本文首先介绍了车辆路径问题的产生背景及定义，然后由此引出并介绍了车辆行驶 路线的类型，以及行驶路线的选择和优化方法，并针对汇集式行驶路线的启发式算法进 行了实例分析。 关键词：关键词：车辆行驶路线，优化，启发式算法 2 目目 录录 1 车辆路径问题的产生背景 3 2
2、车辆路径问题的定义 3 3 车辆行驶路线的类型 3 3.1 往复式行驶路线 . 3 3.2 环形式行驶路线 . 3 3.3 汇集式行驶路线 . 3 4 车辆行驶路线的选择和优化 4 4.1 环形式行驶路线的选择 . 4 4.1.1 环形式行驶路线的优选标准 . 4 4.1.2 数学模型 . 4 4.2 汇集式行驶路线的启发式算法 5 4.2.1 启发式算法概述 . 5 4.2.2 启发式算法求解流程 . 5 4.2.3 启发式算法实例分析 . 7 5 结论及设计体会 . 10 参考文献 . 11 3 1 1 车辆路径问题车辆路径问题 1 11 1 车辆路径问题的产生背景车辆路径问题的产生背景
3、美国物流管理学会(Council of Logistics Management，CLM)对物流所作的定义为： “为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点 至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。 ” 而有关 资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到 52% 之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成 为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。 1.1.2 2 车辆路径问题的定义车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的车
4、辆的集合、一个物流中心（或 供货地） 、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客 户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制 等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等） 。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依 照最短的行驶路线或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本 实现最小。 2 2 车辆行驶路线的类型车辆行驶路线的类型 2 2.1.1 往复式行驶路线往复式行驶路线 往复式行驶路线，是指运输过程中车辆在某一运输路线的两个端点之间做多次（包
5、括一次）往复行驶的路线类型。它又可以分成三种形式：单程有载往复式、回程部分有 载往复式和双程有载往复式。 2 2.2.2 环形式行驶路线环形式行驶路线 环形式行驶路线是指车辆在由若干个装卸作业点组成的一条封闭回路上，作连续单 向运行的行驶路线。由于各货运点在运输方向上的相互位置不同，这种形式的路线分为 三种形式，即简单环式、交叉或三角环式以及复合环式。 2 2.3.3 汇集式行驶路线汇集式行驶路线 汇集式行驶路线是指车辆沿着分布于运行路线上各装卸作业点，依次完成相应的装 4 卸作业，且每运次的货物装（卸）量均小于该车额定载质量，直到整个车辆装满（或卸 空）后返回出发点的行驶路线。般情况下，汇集
6、式路线为封闭路线。车辆可能沿着一条 环 形 式 的 路 线 行 驶 ， 也 可 能 在 一 条 直 线 形 路 线 上 往 返 行 驶 。 汇集式的运输形式一般可分为三种形式： （1）分送式：车辆从起点装车完成后，沿 着运行路线上的各个货运点依次进行卸货，最终可返回起点； （2）收集式：车辆从起点 空车出发，沿着运行路线上的各个货运点进行装货，最终达到目的地； （3）分送收 集式：车辆沿着运行路线上的各个货运点分别或者同时进行装货以及卸货。 当车辆采用汇集式行驶路线完成运输任务时，每次周转的货物周转量的大小与车辆 沿路线上各货运点的绕行次序有关。若绕行次序不同，即使完成同样货运任务其周转量 也不一样。在这种情况下，按总行程最短组织车辆进行运输最为经济。 3 3 车辆行驶路线的选择和优化车辆行驶路线的选择和优化 3 3.1.1 环形式行驶路线的选择环形式行驶路线的选择 3 3.1.1.1.1 环形式行驶路线的优选标准环形式行驶路线的优选标准 选择环形式行驶路线的原则是：当完成同样货运任务时，里程利用率 最高为最 佳。环形式行驶路线以运次为基本运输
