文档介绍：物流系统优化中的定位—运输路线安排问题
(LRP)研究评述* 国家自然科学基金重点项目(70031020)
摘要本文概述了物流优化问题中的定位—运输路线安排问题(Location-Routing Problems, LRP)的发展历程,并对LRP的分类和解决方法加以评述,最后就这一问题的发展方向进行简单地探讨。
关键词 LRP 物流系统优化运筹学
1 引言
新技术的迅速发展,特别是电子商务的风起云涌,为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持,发展势头强劲,但是,由于它是一套全新的技术,同时还是一种全新的管理理念,所以其发展过程中必然存在一些难题。在电子商务“三流”(信息流、物流、资金流)中,随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及,信息流的发展已经比较成熟了;而随着各大银行纷纷开展网上业务,以及支付网关的建立和加密技术的成熟,网上支付已经在许多网站上成为现实;然而,我国传统的物流体系是在计划经济环境下建立、发展起来的,与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之一。所以对物流系统优化的研究将会具有很大的现实意义。
国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了,为各类实际问题构建了优化模型,并形成了许多解决问题的算法。依据实际问题的不同,可以对物流系统优化问题进行分类,比如,运输车辆路线安排问题(VRP)、定位—配给问题(LA)、定位—运输路线安排问题(LRP)等等,其中LRP更贴近目前的物流系统复杂的实际特征,所以对它的研究是十分有意义的。
本文先从VRP和LA的集成来探讨LRP的由来,然后讨论LRP的分类,同时探讨LRP的研究现状,并对LRP的解决方法进行概述,最后就LRP的未来发展方向作简要的讨论。
2 从VRP、LA到LRP——物流系统的集成
依据实际问题的不同,可以对物流系统优化问题进行分类,比如确定设施(指的是物品流动的出发点和终到点,如配送中心、仓库、生产工厂、垃圾回收中心等)位置、运输路线安排、库存控制等,国内外许多学者就各类问题的特征进行了分析,并提出了各类问题的数学模型和解决方法。
运输车辆路线安排问题(Vehicle Routing Problems VRP)
该问题可定义为:运输车辆从一个或多个设施到多个地理上分散的客户点,优化设计一套货物流动的运输路线,同时要满足一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情况已知,由此确定一套车辆运输路线,以满足目标函数(通常,VRP的目标函数是总费用最小)。如图1所示。
图中,□表示设施;〇表示客户;↗表示运输路线
图1 VRP的图示
实际上,VRP是按如下假设定义的最小费用问题[1]:
(1) 所有车辆路线均起始并终止于设施点。
(2) 每个客户只接受一个设施的货物。
(3) 满足其他一些约束条件,如:
■容量限制:每个客户点上都有一个非负的货物需求量,但每条车辆路线上的货物量总和不超过车辆装载量。如果此约束不满足,则引入惩罚函数。
■总时间限制:每条路线总的长度或总耗时不超过一个事先定下的数值。这项限制旨在满足客户对供货时间的要求,以及对货物品质的保证。
■具体时间限制:对某个客户