文档介绍：物流配送车辆优化调度的一种神经网络算法
摘要:本文讨论了物流配送车辆优化调度问题的分类,建立了解决非满载车辆卸货路线优化的神经网络模型,提出了解决配送车辆优化调度问题的步骤,并进行了具体的调度试验,验证了算法的可行性。
关键词:配送,调度,神经网络
0 引言
据统计,美国2000年的运输费用为5900亿美元,%,可见,减少运输费用是有效减少物流成本的重要方面。对于物流中心和第三方物流企业的货物配送,运输车辆的调度是工作的重点,正确合理的调度可以有效减少车辆的空驶率,实现合理路径运输,从而有效减少运输成本,节约运输时间,提高经济效益。
1 配送车辆调度优化问题分类
运输车辆的优化调度问题由Dantzig和Ramser于1959年首次提出,由于该问题在交通运输、工业生产管理等领域具有广泛而重要的应用,因此30多年来其研究得到很大重视,国外的Bodlin,Christofider,Golden,Assad, Ball 等人对该问题进行了较为深入的研究[1] [2] [3]。
总体上看,车辆的优化调度问题一般可根据时间特性和空间特性分为车辆路径规划问题和车辆调度问题。当不考虑时间要求,仅根据空间位置安排车辆的线路时称为车辆路径规划问题(
VRP-Vehicle Routing Problem);考虑时间要求安排运输线路时称为车辆调度问题VSP(Vehicle Scheduling Problem)。某些学者将有时间要求的车辆调度问题称为Vehicle Routing Problem with Time Windows。车辆优化调度问题可根据不同性质具体分为以下几类。
按照运输任务分为纯装问题、纯卸问题以及装卸混合问题,所谓的装卸混合问题就是车辆在运输途中既有装货又有卸货。
按照车辆载货状况分为满载问题和非满载问题,满载问题是指货运量多于一辆车的容量,完成所有任务需要多辆运输车辆。非满载问题是指车的容量大于货运量,一辆车即可满足货运要求。
按照车辆类型分为单车型问题和多车型问题。
按照车辆是否返回车场划分为车辆开放问题和车辆封闭问题,车辆开放问题是指车辆不返回其出发地,车辆封闭问题是指车辆必须返回其发出车场。
按照优化的目标可分为单目标优化问题和多目标优化问题,单目标优化是指某一项指标最优或较优,如运输路径最短。多目标优化则是指同时要求多个指标最优或较优。如同时要求运输路径最短和费用最省。
按照货物的种类要求可分为同种货物优化调度和多种货物优化调度。多种货物优化调度问题是指运输货物的种类多于一种,车辆调度时可能要考虑某些种类的货物不能同时装配运输的要求,如灭害灵等杀虫剂和食品等不能混装运输等。
按照有无休息时间要求可分为有休息时间的优化调度和无休息时间优化调度问题。
实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合,如某配送中心向其多个客户配送货物需要多辆车,这些车的类型不一样,运输的货物种类包括食品、日用品和蔬菜等多类,调度优化时希望运输费用最省,同时也希望运输时间最短,这样问题变为一个多车型多货种的送货满载车辆的多目标优化调度问题。
车辆的优化调度问题是一个有约束的组合优化问题,属于NP难题(Nondeterministic Polynomial Problem),是一个非确定型的多项式问题。NP问题的解有多个,随着其输入规模的扩大,问题的求解难度大大增加,求解的时间呈几何级数上升。目前,尚无有效的多项式时间算法来求解NP难题。
在求解车辆优化调度问题时,常常将问题分解或转化为一个或几个已经研究过的基本问题,如旅行商问题,最短路径问题,最小费用流问题,中国邮递员问题等。再用比较成熟的理论和方法进行求解,以得到原车辆调度问题的最优解或满意解。
常用的方法可以分为精确算法、启发算法和智能算法。精确算法主要有分支界定法,割平面方法,线性规划法,动态规划法等,启发式算法主要有构造算法、两阶段法、不完全优化法等,智能算法分为神经网络方法、遗传算法和模拟退火算法等。
精确算法的计算量随着车辆优化问题规模的增大呈指数增长,如当停车卸货点的数目超过20个时,采用一般的精确算法求解最短运输路径的时间在几个小时以上。精确算法不适合于求解大规模的车辆优化调度问题。
2 配送车辆优化调度的神经网络算法
算法概述
人工神经网络是对人脑功能的简单和近似模拟,它由大量具有某种传递函数的神经元相互连接而成。人们经常采用Hopfield网络和自组织特征映射神经网络来解决车辆的优化调度问题。在Hopfield网络中,系统能够从初始状态,经过一系列的状态转移而逐渐收敛于平衡状