物流配送车辆路径问题_VRP_算法研究.pdf

第 22 卷第 2 期徐州工程学院学报 2007 年 2 月
V ol. 22 No . 2 Jo urnal of Xuzhou Institute of T echnolog y FEB. 2007
物流配送车辆路径问题( VRP) 算法研究
方金城1, 2, 张岐山1
( 1. 福州大学, 福建福州 350002; 2. 福建工程学院, 福建福州 350014)
【摘要】物流配送车辆路径问题( VRP) 属于 NP- hard 问题. 文章介绍了当前最具有代表
性的算法, 分析并总结了各种算法的优缺点及目前的改进情况, 指出目前启发式算法是求解车辆路
径问题的主要方法, 至于大规模客户集的配送路径优化问题或者是多约束的复杂 VRP 问题, 可以
考虑利用多种算法相结合的办法来解决.
【关键词】物流配送; 车辆路径问题; 算法
【中图分类号】 O224 【文献标识码】A 【文章编号】1673-0704( 2007) 02-0084-05
1 车辆路径问题( VRP) 概述
物流配送车辆路径问题( Vehicle Routing Problem, VRP) 最早是由 Dantzig 和 Ramser 于 1959 年首次提
出的. 该问题的研究目标是对一系列的顾客需求点设计适当的路线, 使车辆有序地通过它们, 在满足一定的
约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下, 达到一定的优
化目标( 如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率尽量高等) [ 1] .
一般地, 车辆路径问题可以这样描述: 某一配送中心有V 辆车, 需要对 C 个节点( 客户) 进行运输配送, 每
个节点的货物需求量是 gi( i = 1, 2, ⋯, C) , 每辆配送车的最大载重量是 Q. 设 cij 表示节点 i 到节点 j 的运输成
本, 如时间、路程、花费等. 取配送中心编号为 0, 各节点编号为 i( i = 1, 2, ⋯, C) , 定义变量如下:
1, 车辆 k 由节点 i 驶向节点 j
x ij k = ,
0, 否则
1, 节点 i 的配送任务由车辆 k 完成
yik = .
0, 否则
建立此问题的数学模型:
C C V
minZ = ∑∑∑cij x ijk, ( 1)
i= 0 j = 0 k= 1
C
∑giy ik ≤ Q k = 1, 2, ⋯, V , ( 2)
i= 0
V 1, i = 1, 2, ⋯, C
∑y ik = , ( 3)
k= 1 V, i = 0
C
∑x ij k = y jk , j = 1, 2, ⋯, C k = 1, 2, ⋯, V , ( 4)
i= 0
C
∑x ij k = y ik, i = 0, 1, 2, ⋯, C k = 1, 2, ⋯, V . ( 5)
j= 1
收稿日期: 2006-10-25
基金项目: 福建省教育厅资助项目( JA03006)
作者简介: 方金城( 1977-) , 男, 福建福清人, 讲师, 硕士研究生, 主要从事物流管理、信息系统分析与设计研究.