调度配送（精选7篇）
调度配送 篇1
1 物流配送概述
配送是以用户需求为前提,对货物进行挑选、包装和分配等一系列工作,并将其送至指定地点的活动。配送是物流活动的核心环节,需要完成货物的包装、保管、运输和装卸等多项任务。配送的基本要求是保证货物的种类和数量没有差错,在此基础上保证能够按时送达客户。在实现这两个保证后,力争寻求到更加节约成本且更为快捷的配送方案,以实现利益的最大化。而在整个物流配送环节中车辆调度问题最为重要,与经济效益密切相关。
从1959年首次提出物流配送车辆优化调度问题直至发展到今天,物流配送行业一直致力于在满足一定约束条件下(包括用户需求和现实因素的限制等),选取最为合适的行车路线,争取最大面积覆盖取送货点,优化各项指标,最终实现效益的不断攀升。
2 车辆优化调度问题概述
车辆优化调度问题根据时间特征的差异可分为车辆调度问题VSP(Vehicle Scheduling Problem)、车辆路径规划问题VRP(Vehicle Routing Problem)以及有时间窗的车辆路径问题VRPTW(Vehicle Routing Problem with Time Windows)。其中VSP问题侧重于考虑时间上的要求来安排运输线路;VRP问题不考虑时间因素,仅从空间上对问题进行优化,目的在于令安排的路线更加合理;此外,由于VRP问题的不断发展,在原本根据空间来安排路径的基础上,加上时间上的排程考虑,便成为有时间窗的车辆路径问题VRPTW,特点在于在车辆途程问题之中加入时间窗的限制。
也可进行如下分类:
(1)按送货计划安排分为纯装问题、纯卸问题和装卸混合的问题。区别在于安排纯装问题和纯卸问题的车辆允许在所有任务点装货或卸货。而装卸混合问题比较复杂,装货和卸货可能同时进行,并没有严格界定。
(2)按车辆的装载货物量分为满载问题和非满载问题。安排满载的车辆完成任务时可能需要多辆车,而安排非满载的车辆完成任务时,多项任务仅需一辆车就能完成。
(3)按车辆类型分为单车型问题和多车型问题。单车型要求完成此次任务的所有车辆,其容量完全相同,而多车型并没有此要求,可以搭配安排。
(4)按优化指标多少分为单目标优化问题和多目标优化问题。单目标优化问题仅要求一项指标最优,通常这项指标是该次任务最为重要的指标,而多目标优化问题将考核目标范围扩大,要求多项指标最优或较优,如既要求路途短,又要求运费少。
(5)按时间窗要求分为硬时间窗问题、软时间窗问题。硬时间窗要求车辆必须完全遵照时间安排,早到必须等待,而晚到则拒收。而软时间窗相对灵活一些,可以不在时窗内到
3 车辆优化调度问题研究
车辆优化调度问题可通过精确算法和启发式算法来进行求解。精确算法是根据问题建立数学模型,然后进行求解,具体方法都有割平面法、线性规划法、动态规划法等,精确算法由于设计过于理想,并不具有普遍适用性。启发式算法结合直观情况和经验,是一种逐步逼近最优解的算法,具体方法有构造算法、神经网络法、遗传算法等,启发式算法更为接近实际生活情况,适用范围广泛,正是我们研究的重点所在。
在此介绍几种常用的优化算法:
3.1 遗传算法
J.Holland教授于1975年首次提出遗传算法(Genetic Algorithm,GA),遗传算法源于物种进化的自然选择理论,结合物种进化过程中适者生存规则以及染色体中随机信息的交换,发展形成的一种智能算法。遗传算法的基本思想是:从群体中选择较为适应环境的个体用于繁殖下一代,对选中个体进行交叉、变异等操作,以适应度为选择原则,通过算法的迭代选取最优个体。当最优个体的适应度不再变化时迭代结束,得到全局最优解。遗传算法广泛应用于多项领域,属于智能计算的关键技术。
优点是具有鲁棒性,全局搜索能力强,耗时较短,但是不能保证每次搜索结果一样。
3.2 模拟退火算法
N.Metropolis于1953年首次提出模拟退火算法(Simulated Annealing,SA),模拟退火算法的基本思想是:首先,给定一个初始状态,并设定初始温度和降温次数,同时在邻域范围求出另一个解,结合控制参数选择接受或舍弃,经过反复实验后,求得参数控制下的相对最优解;下一步,构造降温函数,不断减小控制参数的值直至为0,此时获得的解即为全局最优解。前半部分是通过加热增加物体能量;后半部分是通过降温来减少物体的能量。对照数学模型,所构造的目标函数就是物体的能量,故求最优解的过程就是求能量最低态的过程。
优点是有很强的全局搜索能力,但是由于允许移动到较差的解,所以会出现接受目标值不好的状态,仅产生局部最优解,导致求得全局最优解要花费较长时间。此外模拟退火的有效性与邻域的选择相关,若邻域的设计范围合理,算法将更为优越,反之,会影响获得的结果。
3.3 蚁群算法
M.Dorigo于1992年首次提出蚁群算法(Ant Colony Algorithm,ACA),蚁群算法源于蚁群在觅食时发现最短路径的行为,蚁群通过寻找信息素浓度最高的路径,从而找到最佳路径,蚁群算法是一种模拟进化算法。蚁群算法的基本思想是:首先,将多只蚂蚁分别放在不同的初始点处,设定顶点也置于当前解集中,蚂蚁从初始点开始转移,直到所有的点都已存在于解集中,得到各只蚂蚁的适应度,记录下当前最优解;然后更新信息素,迭代结束后,求出种群进化后的最优解,便得到问题的最优解。
优点是求解结果不依赖于初始线路,且不需要人为参与调整,设置较为简单,但需要不断调整变量,过程繁琐,任务量大。
4 当前研究中存在的问题
当前对于物流配送车辆优化调度问题的研究,模型设计比较简单,而且将影响因素孤立开来,使得构造的模型与现实复杂的情况出入较大。其次,典型模型的设计与实际情况不符,如典型模型默认是集货送货一体化的问题。实际上,大部分物流公司的业务是集货任务、送货任务、集送一体化任务混合在一起的,在物流配送中需要综合考虑,统一安排车辆。另外,在模型的设计中并未考虑到一些突发情况,过于公式化,导致在实际应用中比较局限。
5 车辆优化调度问题研究展望
针对当前研究中存在的问题,要想把研究真正与实际相结合,更具有应用价值,应该注重对研究问题的描述,建立与实际情况相符合的模型。其次,鉴于道路交通状况对调度的影响越来越大,将实时交通状况与车辆调度问题相结合是十分有必要的。
物流业和配送业近几年在我国迅速崛起,车辆优化调度问题也日益重要。但是由于我国在这方面起步晚,发展速度缓慢,无法满足日益增长的需求。同时对于通用理论的研究较少,对于应用性研究也过于局限。因此,有必要将研究的部分重心转移到通用性好、运算速度快且精度高的优良算法上来,以缩短存在的技术差距,健全快速发展的物流业,促进经济的进一步发展。
参考文献
[1]张强,荆刚,陈建岭.车辆路线问题研究现状及发展方向[J].交通科技,2004,(1):60-62.
[2]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法[J].中国公路学报,2006,19,(4).
[3]唐小明,郭晓汾.基于物流配送服务水平多指标的车辆模糊优化调度[J].西安工业学院学报,2005,25,(3).
[4]骆义,谢新连.物流配送车辆调度优化研究[J].大连海事大学,2003,(3):7-12.
[5]宋华,胡左浩.现代物流与供应链管理[M].北京:经济管理出版社,2000,11,4.
[6]Hwang H S.An improved model for vehicle routing problemwith time constraint based on genetic algorithm[J].Computers&Industrial Engineering,2002(42):361 369.
调度配送 篇2
在竞争日益激烈的现代商业信息社会,企业只有以市场为核心去适应不断变化的环境并及时对市场做出反应,才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标。合理使用调度运输工具,优化运输路线,降低企业物流成本,是物流管理的重要功能。由于对物流管理中的车辆调度问题的研究对社会经济发展具有举足轻重的作用。因此,国内外学术界对物流运输系统的调度优化问题十分关注。配送是物流系统的一个重要环节,配送业务中,配送车辆调度问题的涉及面广,是配送系统优化的关键,具有很大的分析价值。本文正是基于这个原因才对车辆调度问题进行研究。
2 车辆调度问题的概述
物流配送车辆优化调度问题最早是由Dautzig和Ramser于1959年首次提出的,称之为Vehicle Routing Problem(简称VRP)[1]。
VRP问题一般定义为:对一系列给定的顾客(取货点或送货点),确定适当的配送车辆行驶路线,使其从配送中心出发,有序地通过它们,最后返回配送中心,并在满足一定的约束条件下(如车辆容量限制、顾客需求量、交发货时间等),达到一定的目标(如路程最短、费用最少等)。
车辆的优化调度问题主要探讨:组织的行车路线,能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下,有序地通过一系列供应点或需求点,达到诸如路程最短、费用最小,耗费时间尽量少等目的[2,3]。
自VRP被提出之后,人们在解决VRP问题的时候,综合考虑多方面的因素,如有无时间限制、纯装纯卸或是混合装卸、是满载或是非满载、车型是单车型或是多车型、是单配送中心或是多配送中心以及车辆配送完是不是必须返回原始配送中心等。
2.1 车辆调度问题的分类[4]
车辆调度问题可以细分为VSP(Vehicle Scheduling Problem,即车辆调度问题)和MTSP(Multiple Traveling Salesman Problem,即多旅行商问题)。但是按照大多数人的习惯,对这几类问题不做严格细分,仍统称为车辆调度问题(即VRP问题)。
车辆调度问题可以根据不同性质划分为以下几类:
有无时间限制问题,即我们所说的有时间窗车辆调度问题和无时限车辆调度问题,是指配送货是否必须在一定的时间限制内完成。对有时间窗的车辆调度问题又可以分为硬时间窗问题和软时间窗问题。而硬时间窗问题是指运输任务必须在规定的时间内完成;软时间窗问题是指任务不一定非得在规定的时间内完成,但是超过规定的时间,则会受到一定的处罚。
纯装问题或纯卸问题,即车辆在所有任务点装货或卸货,即集货或送货问题;而装卸混合问题,则是指每项任务有不同的装货点和卸货点,即集货、送货一体化问题。
满载问题,即货运量不小于车辆容量,完成一项任务需要不只一辆车;而非满载问题,则是指货运量小于车辆容量,多项任务用一辆车。
单配送中心问题和多配送中心的问题,则是考虑客户与配送中的距离长短,以便节约企业运输成本、提高运输效率。
单车型问题即所有车辆容量相同,而多车型问题即执行任务的车辆容量不全相同。
车辆开放问题即车辆可以不返回其发出车场,而车辆封闭问题是指车辆必须返回其发出车场。
综上所述,车辆调度问题涉及的内容较广,包括中国邮递员问题、旅行商问题、指定两点之间的最短距离以及任意两点之间的最短距离等问题,所以研究起来较复杂。
2.2 VRP研究动态及水平
车辆调度问题自被提出来以后,近二十年来,无论是国外还是国内,它都是一个发展活跃的一个领域。在国外,VRP问题已经广泛的应用于实际生活,如邮局的邮件递送业务、超市的商品供应、牛奶站的牛奶送达业务、工业产品的传输、快递公司的运输安排,并取得了很大的经济效益。
VRP问题自从被提出以来,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。在经典VRP的基础上,车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态,包括TSP(可看作VRP的一个特例,即当VRP只包括一条路径,且没有能力约束时就成为TSP)、带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW)、,随机需求车辆路径问题(Vehicle Routing problem with Stoehasti Demand,VRPSD)、动态车辆路径问题(Dynamic vehicle Routing Problems,DVRP)等[5,6]。早在60年代Clarke和Wright就提出的节约法(Saving Method)。1962年,Balinski等人首先提出VRP的集分割,直接考虑可行解集合,在此基础上进行优化,建立了最简单的VRP模型。1971年,Eifon等人提出将动态规划法用于固定车辆数的VRP,通过递归方法求解。其后,Christofields提出了状态空间松弛,极大地减少了状态数量。1974年,Gillet和Miller提出的扫描法(Sweeping Method)。1981年,Christofides等人提出了k度中心树和相关算法,对固定车辆数m的m一TSP进行k度中心树松弛。后来,M LFisher对这种方法做了进一步改进,可求解有134个客户的VRP。1991年,Gendrean等人[8],将禁忌搜索方法应用于VRP。其后E Tailiard等人[9]。通过按角度和路径重心对原问题的空间进行分割,再用禁忌搜索结合模拟退火对子问题求解,实现了对问题求解的并行化。1996年,J.Lawrence[10]将遗传算法用于VRP的研究,并可有效求解带时间窗口的VRP。
此外,国外从实用化角度开展的研究也比较多,研究者将模型和算法方面取得的进展应用于很多具体问题。也由此诞生了一些为企业车辆路径提供服务的专业化公司,开发了各具特色的车辆路径软件,比较著名的有:美国ES班公司的Aiclogisties系统,Roadnet科技公司的Roadnet5000系统,Routesmart科技公司的Routesmart系统,Optrak软件公司的OPtrak系统,IBM的VSPX系统,美孚的HPCAD系统,另外还有日本富士通的VSS系统等。
国内VRP的研究起步较晚,国内也有一些对车辆调度进行的研究。李大卫等以TSP的最近距离启发式算法为基础,通过设置评价函数来处理时间窗约束,求解了简单的VRP[7]。张震针对单车场满载问题,提出了考虑运输行程约束的优化方法。蔡延光等应用并行禁忌搜索算法和模拟退火算法对满载问题进行了求解[20]。刘浩等用模拟退火算法求解了两车型随机需求的VRP[11]。张涛等用禁忌搜索算法和遗传算法的混合策略求解了VRP[20]。王莉用启发式算法求解了有时限的VRP[13]。袁健等用神经网络法求解了VRP[14]。姜大立、李大卫分别用遗传算法求解了无时限和有时限的物流车辆调度问题。近年来,郭耀煌、李军、谢秉磊等对物流车辆调度问题进行了较为深入的研究,提出了多种求解算法。周双贵对物流车辆调度问题的模型和求解方法也进行了较为深入的研究[19]。
2.3 车辆调度的目标
车辆调度的目标是以尽量少的路径距离、费用消耗、时间消耗和所需车辆数来可靠地完成汽车调度和货物配送任务。
3 车辆调度问题的研究方法
车辆调度问题的求解算法包括精确算法和启发式算法两个类别。由于车辆调度问题是NP-hard问题,存在高效的精确算法的可能性不大。因此,学者们主要将精力集中在构造高质量的启发式算法上。
3.1 精确算法
精确算法是指可以求出其最优解的算法,主要有:
1) 分枝定界法
此方法是一种隐枚举法或部分枚举法,它不是一种有效算法,是枚举法基础上的改进,是求解整数规划的较好方法。Kolen曾利用此方法求解有时间窗约束的车辆巡回问题,其实验的节点数范围为6~15。当节点数为6时,计算机演算所花费的时间大约1分钟,当节点数扩大至12时,计算机有内存不足的现象产生,所以分枝定界法比较适用于求解小型整数规划问题。Held和Karp指出分枝定界法的求解效率与其界限设定的宽紧有极大的关系,所以分枝定界法比较适用于求解小型问题。
2) 割平面法
此方法与分枝界限法类似,也是在求解与整数规划相对应的线性规划上,不断地增加新的约束,也就是另外加入线性约束条件,以切掉对应于非整数规划的所有可行解的集合,以使问题可达到整数线性规划求解的形式,从而获得最优解。求解时间过长,不适用于大规模问题。
3) 动态规划法
该算法解题的基本思路是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。因其复杂性在于各阶段决策之间的相互联系,而且计算时间与计算机内存空间均随变量的增加而里指数增加.所以虽然此方法可求得最优解,但仅适用于较小规模的寻优问题。第一个VRPTW最优化算法是Kolen等在1987年提出的动态规划算法。
精确算法的计算量随着车辆优化问题规模的增大呈指数增长,如当停车卸货点的数目超过20个时,采用一般的精确算法求解最短配送路径的时间在几个小时以上。所以精确算法不适合于求解大规模的车辆路径优化问题。
3.2 启发式算法
3.2.1 传统启发式算法
传统的启发式算法在求解VRPTW问题时通常是从初始解出发,以邻域搜索的方式实现解的改进,并在较短的时间内获得一个可以接受的解。
1) 节约算法(Saving Method)
算法思想是将每条路线只含一个配送点的n条路线作为初始解,其中,每条路线中第一个和最后一个配送点分别称为路线的起点和终点。考察一条路线的起点与另一条路线的终点相连合并成新的一条路线。如果合并后的路线满足约束条件(车辆容量、时间窗),则认为这样的合并是可行的,并将合并的节约值定义为连接这两条路线的边的节约值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并时,算法结束。此方法的优点是可提高车辆的利用率。
2) 邻接算法(Nearest-Neighbor)
邻接算法是一种序列构造路线法。算法从一条只含一个配送点的路线出发(通常取“距离”配送中心最近的点)。在未分配点中筛选出可加入点(未分配点且可行),并从可加入点中选取一个点作为当前路线的终点,使得路线的成本最小。如此不断对路线进行扩充,直到路线不存在可加入点为止。这时,如果所有点均已分配,则算法结束;否则,生成一条新的初始路线,重复前面的路线扩充程序。
3) 插入算法
插入法是结合邻接算法与节约算法的观念,依序将顾客点插入路径中以构建配送路线。它的流程与邻接算法相似,也是从初始路线出发,序列构造路线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。
4) 扫除算法
扫除算法是一种“先分组后路线”的算法。所谓分组,即指分派给每辆车一组点。一种简单的分组方法是将以车站为原点的坐标平面划分为多个扇形区域,并初步将每个扇形区域的点分派给一辆车。而所谓的“路线”,是指在每个区域内,采用扫除法选择未分配点,然后应用插入算法扩充路线。如果在进行了一次“分组——路线”的路线构造后,还存在未分配点,则再进入“分组——路线”程序。如此反复,直到所有点均已分配为止。
3.2.2 现代启发式算法
相对于传统启发式算法,现代启发式算法不要求在每次迭代中均沿目标值下降方向,而允许在算法中适当接受目标值有所上升甚至不可行的解,其目的是能够跳出局部搜索邻域。
1) 禁忌搜索算法(Tabu Search,TS)
禁忌搜索算法是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的局部最优点,并在后面的搜索中,根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。
2) 遗传算法(Genetic Algorithms,GA)
遗传算法是借用适者生存规律进行局部搜索改进的一类算法。该算法通过染色体的配对和变异过程实现种群的进化,每一次进化则对应解的一次迭代。当迭代次数达到最大次数限制或群体中的个体无显著差异时,迭代终止。
3) 模拟退火算法(Simulated Annealing,SA)
1996年,Chiang和Russell提出VRPTW问题的模拟退火算法。模拟退火算法实际上是一种随机松弛技巧,它模拟了退火过程。在搜索的初始阶段,算法跳向远点,随着时间的延伸或“降温”,跳跃幅度逐渐减小,最终转向局部搜索下降方法。
4) 蚁群算法(Ant Colony Optimization,ACO)
蚁群算法模拟了蚁群搜索食物的行为。在寻找食物时,蚂蚁会在它所经过的路径通过排放一种外激素(pheromone,在算法中称为信息素)作出标记,排放的量则根据路径长度和食物的等级决定。这些外激素为其它蚂蚁提供信息,并吸引他们前去搬运食物。算法中,首先构造两组相互协作的人工蚁群,其中第一个蚁群用于最小化车辆数,第二个蚁群用于最小化总路长。并以共用解的方式建立协作关系。
4 各种车辆调度优化算法的比较分析
大家知道,各种优化算法都有其一定的不足之处,不然的话也就不会有这么多的优化算法了。各种优化在一定时期、一定的情况下都有各自的优点,都有解决某一类问题的优越性,但随着发展的需要,对优化方法的要求也就越来越高了。下面对上面所述几种优化方法进行比较分析,通过表格的形式来展现各自的特点。
通过表1我们可以看出精确式优化算法求解是最优解,但只适用于小规模的VRP问题,而不适用于求解复杂的VRP问题,求解复杂的VRP问题时费时又费力,且难以实现。
物流配送的车辆调度排班问题分析 篇3
将目标货物从发货人送至收货人的过程被称为配送。由于配送最终的目标是收货人,即为消费者,因此,配送也是物流系统中的一个至关重要的步骤。配送不仅仅局限于配货和送货。满足客户的需求,配送需要在满足客户对货物种类数量的基础上,在保证按时送达客户的基础上选取更快,更节约成本的配送方案,实现利益最大化。
2 物流配送的流程
随着物流配送的发展,现代的物流配送水平的提高,货物流通性大大增强,配送环节取代存储环节成为物流中最重要的部分。而作为配送的核心配送车辆对货物的集货、配送和送货过程越来越被重视,如何选取最优配送路线,是对整个物流质量的考验,关系着物流整体的运输速度,服务成本和经济效益。随着电子商务的崛起,许多国外物流企业如UPS、Fed EX、德国邮政等公司已经从单纯的配送业转型成为以集货作业和配货作业作为主体的新物流模式。
3 车辆优化调度问题的现状
在我国境内,车辆调度问题的发展比国外晚发展近乎三十年,所以现在我国对于较为复杂的车辆调度路径问题研究还是相对落后。由于我国对这方面研究起步较晚,对于通用理论研究不够深入,再加上我国对于应用研究的问题提出虽多但在具体算法上的改进并没有创新,所以我国在车辆优化调度的问题上根本无法满足配送业和物流业的发展需求。随着物流业在市场上的地位日益重要,为了克服我国在车辆优化调度上局限性较强的弱点,我国逐渐开始对车辆优化调度问题进行深入的研究。
4 配送的算法
例如在现实生活中,会有配送中心的多台配送车辆为多家客户送货的情况,如果每个客户的位置和货物需求量一定,运输车的容量相同,每辆车运送货物后要返回配送中心,为防止超载,在考虑配货的同时更应注意每条配送路径上客户的需求量之和不能大于运输车的载量,更要满足每个客户需求。解决此类调度问题有很多方法,根据这些方法在算法上的本质研究可分为三大类,即精确算法、启发式算法、动态求解算法。
4.1 精确算法
精确算法又称最优化算法,是指求出最佳解的算法。其算法有很多,比如切割平面法,网络流算法等。
精确算法有一个弊端,就是其计算量随着需要解决的问题规模的增大而大幅度的增大。由于这个弊端,精确算法只能适合解决规模较小的问题。因为精确算法适应能力较差一般这种算法最适合解决一个特定的问题,所以在实际应用中这种算法不是很受提倡。
4.2 启发式算法
启发式算法完全不同于精确算法,它追求的是解决问题的满意性而不是最优性。它是一种用直观、经验构造出来的算法。到目前为止,启发式算法已经有好多种,最主要是以下两种算法。
构造启发式算法,其实质就是按照标准将不在同一条线路的所有点逐个的增加进来。在算法的每一步上,都要将当前的线路构形和另外的线路构形比较后,综合改进得到最后可行的构形。这类算法的的代表算法是:最邻近法、扫描法、节约法等。
智能化启发式算法就是在人工智能的启发式算法的基础上发展的。它的主要算法有:蚁群算法、神经网络算法等。
5 动态优化策略
动态车辆调度问题相对前两种比较其问题的规模较大解决起来相对比较困难些。并且这种算法的要求是在短时间内就要相应的实时信息。从求解策略上把动态求解算法分为重新优化策略和局域优化策略。
5.1 优化策略
重新优化策略就是当接收到一个新的实时信息时,要重新开始寻找始发到结束的最优车辆的行车路径。实质就是静态方法解决动态问题。研究运送大宗商品的车辆调度问题就是一个较为成功的运用重新优化策略的例子。还有在动态单车问题上,采用了乘子调整技术的静态算法。其算法过程是:当有新实时信息时,就采用动态重新优化法解决,可是这种算法最多能解决十种问题。
局域优化策略的实质是:提前拟定一些路径的模板,当收到实时信息时,就在提前拟定的模板里进行搜索,找个适合的路径进行使用。这种策略和重新优化策略相比较,路径可能是较差的,但是计算量是大大的减少了,从而节约了许多的时间。局域优化策略在实际的车辆调度上比较适用,所以受到重视和进一步的研究。
5.2 实际问题的解决
现代物流企业的核心任务就是合理优化配送资源。在终端物流企业配送的体系中,货物的配送是由总仓库运输到子库,子库到各大营销点。这个过程中的运用统筹学中的知识解决配送安排运输的问题,这个问题P可以这样描述:设子库的集合是A,配送车子的集合是B,A和B集合中的元素是一一对应的。现在有n项运输任务,其总集合记作N,将货物需求量的总集合记作G。将以上的零售点、子库道路、车辆、运输任务、货物运输这些量制作一个网络图。这个任务的要求是所有的参与配送车辆的任务中,需要的配送车辆数、运货的数量、运输路线等顺利完成后使其总的费用是最少的。
对于上述的终端物流配送的显著特点是面向对象是零售户,零售户的特点就是对货物的需求量很少。因为这个,所以这个问题就转变成了一个非满载的车辆调度问题。这个问题比较复杂,其复杂在每个子库就是一个MTSP,这个TSP的特点是可以有重复的路线。在这个问题上,一辆车的载量是有限的,而且每个零售点的需求又是固定的。从上述可以证明这个问题又是一个非确定性多项式NP,在求其解的过程中,计算量的大小变化是随着点n的增长而增长,并且还是呈指数倍增长的,这就给计算增加了许多困难。
通过对上述问题的分析,实属NP难题,由于实际应用中点的个数n会不断的增大,这就给计算最优解造成一定的困难。我们可以按照这样的思路进行分析求解,将问题P简化成四个问题,即子库分派、车辆分派、线路确定、迭代优化。通过对这四个问题的分析,针对每个问题,根据集合的划分,利用适合解决问题的算法进行求解,严格按照各个算法的实现步骤,最终达到解决总的NP问题的效果。
对于问题P来说,要想解决它就要求出各点之间的最短距离,不论采用的是什么算法,这时间复杂度大约是O(n3)[6]。在上面的算法中,在经过P1到P2过程中就减少变量N的数值,最后使得终端物流配送N的值建好为70左右。因为P3的时间复杂度为O(n4),相比较后可以看出这个算法是可行的。在算法中只要确定了P2,还安排最优的P3的线路,这样整体的优化程度已经完成。NP问题中的车辆分派算法有效的在一开始就得到了较优解。因为在P1到P3问题的解决上得到的都是较优解,所以对于P4问题可以根据具体情况选择执不执行。通过对上述问题的模拟试验,大量的配送计算问题可以在仅仅15分钟内完成。
6 结语
随着物流业和配送业在市场上的发展需求逐步扩大,车辆优化调度问题就日益重要。国外在车辆优化调度问题上发展较快,已经在生产和生活方面广泛应用并且得到了很好的经济效益。可是我国在车辆优化调度问题上的发展起步较晚,发展速度相对较慢,不能满足我国经济发展的需求。所以为了使我国国民经济发展迅速、人们生活质量的提高,就要在物流配送业上大力研究发展车辆优化调度问题。其主要研究方向就是:根据车辆优化调度的分类标准,以及各类问题上的特点应该按照何种算法进行优化;在基本算法的基础上针对特点问题如何改进;在不同地理环境和运输特点的基础上结合车辆优化调度问题上的优化算法,设计出更加适用的优良算法。按照这个方向研究发展,车辆优化调度的问题在现实生活中的意义会更加重要。
参考文献
[1]郎茂祥.配送车辆优化调度模型与算法[M].北京:电子工业出版社,2009,6.
[2]张之富,余静.基于改进遗传算法的车辆优化调度研究[J].中国水运,2009,(4),113-115.
调度配送 篇4
在越库配送中,为了实现准时制配送,降低库存,必须对车辆调度进行深入研究,国内外许多学者均致力于此方面的研究。文献[1]针对美国邮电局邮件优先投递传送系统的卡车运输网络进行了设计,利用整数规划松弛法解决大规模系统的物流配送网络,为解决类似模型提供了依据。陈火根[2]等人针对在已知配送中心位置、客户点位置及道路情况下,对m辆车n个客户点,确定车辆分配(每辆车负责的客户点)及每辆车的行车路线,所采用的方法为遗传算法。林方明[3]等人研究了运输网络优化问题在物流配送决策中的作用,并探讨了物流企业应如何设计运输网络,提出运输网络优化的方法,以降低供应链成本,提高客户响应度。本文作者[4]针对越库作业调度问题提出两阶段越库作业调度模型,并给出了求解该类问题的动态规划算法。本文则是基于遗传算法来设计与上述问题不同的越库配送中心车辆运输网络。
1 问题描述
本文所研究的问题为越库配送中心车辆运输网络的设计,在配送中心内部某些客户需要的货物较多且可以直接从供货商或上级分销商处运走,而无需经过配送中心的整合运输,因此主要考虑车辆是否直接从出发点或通过配送中心将货物运输至目的地,以及每条运输线路上车辆的分配。例如,在连锁超市行业中,门店的货物主要通过配送中心集中进货与供货,在降低门店库存的同时,必须保证门店货物供应的及时性,以提高顾客满意度。因此,必须对配送中心的配货车辆及线路进行设计,从而保证货物及时、准确的到达指定地点,降低运输成本。为了更好地研究配送中心车辆调度问题,我们通过建立模型实现配送中心的车辆调度,确定各条线路上需要的车辆数(起点到终点、起点到配送中心)以及车辆线路安排。
图1描述了该模型的运输网络,由图可知:起点到终点的运输方式,可以是直接运输,也可通过配送中心整合后运输到终点。评价运输方式好坏的指标是运输成本。其数学模型如下:
式中:变量O,R,D为卡车数量,x表示流量。i为所有车辆起点的集合;j为终点集合;K为越库配送中心;xkij为经过配送中心由起点i到终点j的流量;xij为直接从起点i到终点j的流量;Rij为线路ij上由起点i开往终点j的车辆数;Oik为线路ik上起点到配送中心K的车辆数;Dkj为线路kj上配送中心到终点的车辆数;cij为一辆卡车从i到j的费用;C为卡车的承载能力;Sij为起点i到终点j的需求量,且xij≥0,xkij≥0,Rij=0,1,若车辆经由起点i开往终点j,则Rij=1,否则Rij=0;Oik,Dkj为正整数;同时假设所有满载的卡车不经过配送中心而直接从起点i开往目的地j,即Sij≤C。在上述模型中,目标函数为最小化运输成本。约束条件(1)保证所有的目的地都通过直接运输或经过配送中心运输来满足需求。约束条件(2)、(3)保证经过配送中心运输的卡车都尽可能装满。约束条件(4)保证直接运输的卡车都尽可能装满。(注:由于满载卡车直接从起点i直接运到终点j,因此其载货量不超过Sij)。
2 遗传算法的建立与求解
求解车辆调度问题的方法很多,常用的有旅行商法、动态规划法、分支定界法、方案评价法等。遗传算法的出现为求解物流配送问题及车辆优化问题提供了新的工具。许多学者利用遗传算法求解该类问题[5,6,7]。基于所研究问题的复杂性及问题的特点,本文亦采用遗传算法进行求解,下面针对算法具体参数进行研究与分析。
由于此模型中约束条件较多,在解决消除约束条件是需采用修改可行解的方法,其解空间为这种方法使个体的编码由两部分组成,前面部分的Rij的取值为,*01+,而后面的xkij需要根据Rij的值来修改,因此选用二进制编码作为个体的编码方式。
2.1 适应度函数。
针对本文研究的模型,不能直接简单地将个体解码后直接代入目标函数中计算目标函数值,从而衡量个体的适应度。因为对于具有实际意义的模型,各个变量均有严格的约束条件,而个体在进化过程中,无法保证一直满足约束。因此,即使得到的目标函数值很小,但只要不满足约束条件,该个体依然属于“劣质”个体。为此,需要对约束条件进行处理,使对个体好坏的评价更加符合实际情况。
2.2 采用修改可行解的方法消除约束条件。
很多研究表明:惩罚函数法消除模型约束条件在运输问题中并不是非常有效,其主要原因是在约束条件非常多,且约束严格的条件下,个体通过交叉变异很难找到可行解,因此很难找到一种合理的惩罚函数,使选择算子尽量地选择可行解,同时不破坏群体的多样性。DNA技术发展提示我们:依据医学技术,对遗传因子进行人为修改,使它具有我们想要的特征[8]。基于这种启发,设想对于本文所研究物流模型的遗传算法,作如下变换:在由个体基因型解码后,计算个体适应度前,增加处理个体表现型的过程,使其满足模型的约束条件。通过采用修改可行解的方法消除上述困难,且改进后的算法在较短时间内即可获得满意解。同时,修改可行解的方法也在很大限度上减少了解空间的编码长度。其具体做法如下:模型初始的解空间为
对于一个个体的代码,先通过解码得到解的形式,然后根据Rij的值得到xij的值,再根据xij的值修改相应的xkij,最后通过修改后的xkij值,计算得到Oik、Dkj。然后根据Rij和Oik、Dkj的值计算目标函数的值,作为适应度函数的值。通过修改可行解的方法,将个体的解空间精简到对于一个配送中心的配送系统模型,其代码长度缩短了。配送中心数量在一个以上的模型中,代码长度缩短的程度也相当可观。通过数值实验表明,代码长度直接影响算法的计算时间,通过修改可行解的方法大大减少了算法计算的时间。同时由于规模较大时,代码长度可能会超出编程语言的限制,因此,只能通过减小群体大小的方法来满足该限制。修改可行解的方法则最大限度地保证了可以取得足够的群体大小,使遗传算法有效的找到模型的满意解。
2.3 初始群体的生成。
针对该模型特点,提出了初始群体的生成方法(把它命名为确定式随机生成):假设群体大小为M,个体顺序按照0,1,…,n,…,M的顺序,分别在!0+i*j*n/4M,i*j*3/4+i*j*n/M"范围内的代码设置尽可能出现1,其它前i*j的代码为0。但这样,无疑在!i*j/4,i*j*3/4"范围内1的出现的频次远大于其它位置,然后,随机将该值改成0。这样,每个位置的“0”和“1”出现的概率都一致,但不同的个体,“0”和“1”在不同的位置上,出现的概率不同。对于长度很大的代码,可以尽可能的增加个体差异性,增大交叉算子的效果。
2.4 遗传操作。
遗传操作包括三个基本遗传算子:选择、交叉和变异。基于所研究模型的特点,选择算子采用确定式采样选择:由于算法的适应度就是模型目标函数的值,虽然不同的配送方案目标函数的差异很大,但轮盘算法依然很难保证选择尽量多的个体。而确定式采样选择可保证选择尽量多的个体,同时改进了选择算子,以保证遗传群体的多样性。交叉算子选择多点交叉:由于个体编码长度非常长,因此可采用多点交叉,以保证编码充分的交叉,增加全局搜索的能力。同时,基于编码的特点:前i*j个代码为直接运输的决策变量,它们对模型的影响要远远大于后面的其他代码。而后面的代码可能由于前面代码的变化而做出相应的修改。因此变异算子也要做出相应的修改。
在遗传算法前期,为了增加算法的全局搜索能力,对前i*j个代码进行变异,而前i*j个代码每个代码表示一个基因表现型,所以变异算子步骤如下:(1)随机产生一个变异概率pr,决定一个群体中变异的个体数量。(pr*M为整数);(2)随机产生pr*M个0,#M$的整数,确定变异的个体;(3)对每个个体产生pm*i*j个%0,pm*i*j&的整数,确定每个个体的变异基因的个数和位置,并对其取反。
遗传算法后期,主要增加的是算法的局部搜索能力,所以变异的主要基因作为i*j个代码后面的代码,方法和上面的一致。
同时,在算法后期改变变异算子的变异方法。由于编码的特点,前面对Rij的变异更多地影响着全局搜索能力,而后面xkij的变异则增加了算法的局部搜索能力。更加符合算法的原理:先增大全局搜索能力,寻找比较满意的结果,然后通过局部搜索找到足够满意的解。
3 数值试验
为了验证算法的有效性,下面用实例来比较。实例如下:在某连锁零售超市企业,其配送中心负责7个门店的货物供应,同时,所需货物须向7个供应商订货。根据其某一时期的需求量和各线路的运输费用,通过算法获得车辆的最佳调度模型。每辆卡车的载货量为20,需求情况和运输路费情况如下所示:
对于整数规划问题可用Lindo软件,因此下面就用该软件求解此模型。同时将门店和供应商数量增加为8个和9个,进行比较。得到了如下结果:
采用遗传算法求解时算法参数如下:二进制编码、随机生成初始群体、确定式采样选择算子、群体大小为200、遗传代数500、交叉概率0.8、交叉点个数5、变异个体个数概率0.05,变异点概率0.03、遗传90%代后改变变异算子。通过算法计算得到了如下的结果:(同样通过10次计算,得到10组满意解的钧值、方差,以此与Lindo计算情况作对比)
算法得到的满意解与最优解的误差分别为0.78%、0.22%、-2.6%。其中-2.6%,其原因为Lindo所用分支定界法无法求得最优值,程序内存溢出前各分支的最小值。由结果分析可知:对于小规模越库配送系统,此算法可以在很短的时间内得到满意的结果。而当供需商达到各9个时,算法在30秒内计算得到的满意解,比Lindo计算的满意解更接近最优值,且计算时间缩短了近十倍。测试结果充分表明该算法的有效性和快速性。
对于大规模配送系统,可行解比小规模配送系统更具有多样化。可能无法如同小规模配送系统案例那样,在算法遗传500代就得到足够满意的解。对于超过50个供应商、50个门店,以及3个越库配送中心的案例,也可以在30分种内完成500代的算法计算。由遗传算法的原理可知,遗传代数和计算时间之间为线性关系,可以通过在可行的时间内,通过增大遗传代数的方法得到足够满意的解。
4结束语
本文研究了越库配送网络系统中车辆调度问题,在给出问题的数学描述后,提出了求解该问题的遗传算法。算法特点为:(1)采用修改可行解的方法消除约束条件;(2)在算法后期改变变异算子的变异方法。
另外,本文的研究主要针对配送中心网络,通过研究运输车辆调度问题来减少网络中的运输费用。通过数值实验,还可以看到配送系统合理设计取得的经济效益。对于一个较小规模的7个供应商、7个门店、1个配送中心的案例,如果不经过配送中心的配送,而是直接运输,得到的运输费用为654。而通过配送中心配送的最佳运输方式的费用为382。这种规模经济效应还会随着配送网络系统规模的增大而增大。由此可知物流配送技术的前景,同时说明了研究物流配送技术的重大意义。
摘要：针对物流配送中心车辆调度问题,采用混合整数规划方法进行建模。对实际问题进行研究分析后,基于所研究问题的特点,提出基于遗传算法的求解方法。通过数值实验对算法不同参数组合进行分析、比较,获得最佳参数组合,建立了有效的求解该问题的遗传算法。并通过对实际问题的数值仿真试验,验证了算法的有效性。
关键词：配送中心,车辆调度,优化,遗传算法
参考文献
[1]Harvey Donaldson,Ellis L.Johnson,H.Donald Ratliff,Mei Zhang,Schedule-Driven Cross-Docking Networks[R].Technical report.The Logistics Institute,Georgia Institute of Technology,Atlanta,GA.2003.
[2]陈火根,丁红钢,程耀东.物流配送中心车辆调度模型与遗传算法设计[J].浙江大学学报:工学版,2003(5):512-516.
[3]林方明,马建军,庞渊.物流配送决策中的运输网络优化问题研究[J].山西建筑,2004(8):84-85.
[4]马东彦,陈峰.以总加权完工时间和为目标的约库作业调度问题及其动态规划算法研究[J].上海交通大学学报:自然科学版,2007(5):852-857.
[5]孙福春,宁槟.遗传算法在车辆调度问题中的应用[J].交通与计算机,2005(2):21-23.
[6]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000(3):35-40.
[7]王惠,陈燕.基于遗传算法的多目标的有时间窗的车辆调度[J].计算机应用,2004(9):144-147.
[8]陈曦,林涛,唐贤瑛.遗传算法的参数设计与性能研究[J].计算机工程与设计,2004,25(8):1309-1310,1319.
[9]姚城.物流配送中心规划与运作管理[M].广东:广东经济出版社,2004.
调度配送 篇5
1 成品油配送中车辆优化调度的过程分析
在成品油的储运过程中, 最核心最关键之处就是要加强物流配送车辆的优化调度, 要确保物流运输的合理化, 这是控制成本、增强企业竞争力的关键。配送体系是由多个配送中心组成的有机体。物流配送中心车辆调动的过程, 其实就是立足于总体的配送目标, 采用系统原理, 选择交通路线和交通工具, 组织交通运输活动, 争取做到最快速度、最短路径、最少消化以及最少环节。成品油配送中车辆的优化调度其实就是通过对路径、交通路线以及交通运输工具等各个方面的选择来优化调度方案的过程。
2 车辆调度优化的基本方法
在车辆调度优化系统中的调度优化问题较为复杂, 为了降低求解难度, 一般来说, 我们会将技术难题加以分解和转化, 将其转化成为已经研究过的基本问题, 进而加以求解。基本问题包括但是不限于以下问题:分派问题、背包问题、旅行商问题、最短路问题、运输问题以及中国邮路问题等等。常用的方法主要是线性规划法、匹配理论、组合理论、统计分析、经验分析、动态规划法、割平面法等等。
3 物流配送车辆优化目标及调度模型
成品油的汽运过程中, 不同的货运任务, 需要的车辆数量是不同的, 再加上每个货运任务都有其集货点和送货点, 这就需要我们结合具体的情况来确定车辆行驶路线进行车辆优化调度。
首先, 按照货主的要求送货以提高物流服务质量, 这也是我们优化的中心目标之一。其次, 从节约成本和提高经济效益的角度规划物流配送的相关要素, 即追求配送时间准确性的前提下尽可能地追求成本最低化;最后, 追求空载率最低化, 即追求配送车辆的最大载重利用率。
我们会将车辆调动问题整合成各种存在一定关系的模型或者凸轮, 一般来说, 模型主要分为三种:以物流为基础的模型、以车流为基础的模型以及集覆盖模型。
4 车辆优化调度问题的分类研究
4.1 非满载车辆优化调度
当货主要求的成品油数量比运输车辆的容量小时, 车辆在运输过程中是以非满载的状态运行, 此时可以考虑让一辆运输车执行多项任务, 也就是说让不同货主的成品油装载于同一辆运输车进行运输。这里主要包括以下两种情况:
4.1.1 集货或送货单独进行
物流的运输是全部由集货点 (装货点) 或送货点 (卸货点) 车辆空车从车场 (泛指车辆出发地, 可以是车库、货场、仓库、配送中心等) 出发, 去各货主处装满货后返回车场, 或是车辆装满货物去各货主处卸货后返回车场。此时, 成品油运输总量低于一辆运输车的装载量, 完全可以由一辆车来执行多项任务, 称为有容量限制的TPS问题。
4.1.2 集货和送货一体化
集货和送货一体化是指成品油的每一次运输都存在着其集货点和送货点, 车辆一般先统计到集货点进行装货, 进而统一到送货点卸货, 在运输任务完成之后, 车辆要再次回到原先出发的车场。如果集货点和送货点较为分散, 并且货运任务容量较大的情况, 容易造成车辆空驶, 货物难以混装;相反情况, 可以安排一辆车在几个集中点装卸。
4.2 满载车辆优化调度
当货主要求的成品油数量较大, 超过运输车辆的容量时, 进行成品油配送的车辆可能远不止一辆, 为保证货主货物量, 车辆一般为满载运行。满载成品油的货车, 从车场出发到几个集货点装卸后返回车场 (仅有装货) , 或是车辆出发到几个送货点卸货 (仅有卸货) 后返回车场。此时的车辆优化调度按照车场的不同, 可分为单个车场的优化调度与多个车场的优化调度。运输车辆来自同一个车场时, 由于每项任务的货物量较大, 每辆车只能去执行一项任务, 这时, 车辆直接从车场到任务点装货 (或卸货) 后返回车场。运输车辆直接按照出发地与运输地的最短路线运输即可, 不需要对运输线路进行优化。运输车辆来自不同的车场时, 即从多个车场出发的车辆到多个任务点执行运输任务, 这种情况即为运筹学中的一般的运输问题, 一般用表上作业法解决运输问题。首先确定初始基可行解, 按单位运价的大小决定供应的先后, 优先满足单位运价最小者的供销要求, 即从单价中最小运价确定供应量, 逐步次小, 直至得到m+n-1个数字格;其次, 进行解的最优性检验, 通常采用闭回路法计算空格 (非基变量) 的检验数;最后, 进行解的调整, 即从检验数为负值的格出发, 做一条除该空格外其余顶点均为有数字格组成的闭回路, 在这条闭回路上对空格的运量作最大可能的调整。需要指出的是, 运输过程中是以卡车为单位, 车辆不装满的话就不能实现效益最优化, 而整数解性质可以避免运输方案为小数的麻烦。
参考文献
[1]孟小平.物流配送及其运输调度优化研究[D].大连海事大学2001.
[2]宋洁蔚, 荣冈.成品油配送中时间窗的确定及运输的安排[J].系统工程理论与实践.2003 (04) .
调度配送 篇6
本文在现有研究成果的基础上,建立了多车型配送车辆调度问题的基于直观描述的数学模型,考虑的目标函数和约束条件比较接近实际,决策变量、目标函数和约束条件的表示较为自然、直观和易于理解.
1. 对多车型配送车辆调度问题的描述
现实中的多车型配送车辆调度问题十分复杂,为了方便建模和求解,需要对现实问题进行一些抽象和简化. 现对本文研究的多车型配送车辆调度问题作如下描述:
1) 从一个配送中心向多个客户送货,配送中心供应的货物能够满足所有客户的需求;
2) 各个客户需求的货物均可以混装,单一客户的货物需求量不超过配送车辆的最大载重量,每个客户的送货要求必须满足,且仅能由一辆车完成,不允许分批配送;
3) 配送车辆按载重量分类,每种车型的最大载重量一定且不允许超载,每种车型的一次配送最大行驶距离一定,不允许超过. 配送车辆均由配送中心出发,向一些客户提供配送服务,最后返回配送中心;
4) 配送中心与客户之间及客户相互之间的最短距离已知且固定.
在满足上述条件下,我们要求运输成本最小.
2. 构建数学模型
现有一个有向图G = (V,E),其中V = {0,1,…,N}有N+ 1个顶点,E = {( i,j) | i,j∈V,i≠j} 表示弧集,顶点0表示配送中心,剩余的顶点集V' = V {0}表示N个配送点,为构建多车型最小费用车辆路径问题数学模型,定义以下参数:
gi: 配送点i的需求量;
φ = {1,2,…,L} 为车辆类型的集合,类型总数为L;
Kl:l车型的数量;
φl:车型l的车辆数集,φl= {1,2,…,Kl};
dij: 两个节点间的最短距离,i,j∈V;
Ql: 车型l的装载能力,Q0l表示车型l的空重;
cl: l型车每公里每吨的载重费用,单位:元/吨·公里;
则目标函数与控制条件如下:
式(1) 表示目标函数,即总配送成本最小;
式(2) 保证车辆都是从配送中心出发,最后回到配送中心;
式(3) 表示进入每个货物需求点的车辆卸载后会离开;
式(4)、(5) 确保每个货物需求点只能被一辆车服务一次;
式(6) 表示车辆承载的货物量之和不得大于车辆的容量;
式(7) 是递推车辆行驶路径的总车质量;
式(8) 是车辆回到配送中心时车辆的重量;
式(9) 是不超过车辆的装载能力;
式(10) 是经过某一配送点时车辆重量不能小于空车重量;
式(11) 是l型车的第k辆从第i点到第j点的费用计算公式.
3. 算法过程
在多车型低耗车辆路径问题解决过程中,本文采用爬山算法作为求解的主要算法. 爬山算法是一种局部择优的方法,它采用启发式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策. 该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解. 属于人工智能算法的一种. 爬山算法结构比较简单,在某些情况下,整体效率还是很好的. 但它的主要缺点是有时会陷入局部最优解,而不一定能搜索到全局最优解. 但由于它求解时可以把复杂问题简单化,且解的结果与最优解比较接近,所以在很多领域中都有着广泛的应用.
爬山算法的基本步骤如下:
第一步:输入多车型低耗车辆路径问题,包括配送中心、顾客点之间的坐标,配送点需求,车型参数(载重能力、空重、不同车型固定成本) 等. 任意选定一个初始解x0,记录当前最优解为xbest,且令xbest= x0,令U(xbest) 代表xbest的邻域.
第二步:从xbest的邻域U(xbest) 中按照某一规则选出一个解xnow,转到第三步;
若当U(xbest) = φ时,或满足其他停止运算的规则时,转到第四步;
第三步:计算xnow的目标函数值min Z1,若xnow的目标函数值min Z1小于xbest的目标函数值min Z,则xbest= xnow,min Z= min Z1,U = U(xbest),转到第二步;否则U = U - xnow,转到第二步;
第四步:输出计算结果,停止.
在爬山算法中,第一步的初始解可以采用随机方法产生,也可以用一些经验方法或者采用其他算法得到初始解.第二步中在U(xbest) 中选取xnow的规则也可以采用随机选取的规则.
4. 实验计算和结果分析
实例:设配送中心(0,0) 和16个客户配送点分布及需求情况,具体数据见表1,假设该配送中心有3种车型,见表2. 根据以上的爬山算法,我们应用Lingo语言来求解,获得费用最少的行驶路径,见表3,此时费用为3654. 40元.
5. 结论
总的来说,对于复杂的VRP,如果仅凭决策者的经验,是很难在较短时间内作出一个合理的运输路径规划的,本文利用优化模型,采用爬山算法,再通过Lingo自动搜索得到费用最少的最优路径和车辆调度数. 最终结果是比较令人满意的.
摘要：多车型多路径的单个配送中心的车辆调度优化是城市配送中的典型问题.针对该问题,本文从空驶成本、运输成本两个维度构建了一个VRP的数学模型,并采用爬山算法对模型加以求解.通过实例仿真,获得其最低运输成本的方案.
调度配送 篇7
一般意义上的物流配送运输调度,指配送中心按不同的客户的多频度、小批量的要求进行组织配送,其主要内容根据确定的配送货物量分配车辆和选择的优先路线。
2 物流配送运输调度成本的构成
区域物流在配送调度成本方面,主要包括货物、车辆、物流中心、分站点、运输网络等造成的各项费用的使用和支出。
2.1 货物
货物指配送的对象,可将每个用户的所下单需求的货物看成一个批次的货物,每批次货物都包括其自身的品名、包装、毛重、净重、是否属于限时达商品等属性。货物自身的属性,造就了其在由分拣中心发往分站点这一区域物流作业中的不同费用的产出,肆意增加这种产出会对每公里物流成本造成极大的浪费。
2.2 车辆
运输车辆作为区域物流中最普遍快捷的承载工具之一,其主要根据装货量的不同而对货物进行不同的装运。车辆的使用应尽量遵循最大装载率,最小使用频次的原则,否则每趟货物都要承担相应的车辆使用费用、支付人工薪酬以及相关费用等。
2.3 物流中心
区域物流重要的工作成所之一,根据客户下单所需配送地点的不同,进而由仓库摆渡到不同的区域物流中心进行后续工作。对于物流中心的位置的不同而造成不同的配送成本。如若物流中心的选址便于所在区域物流的后续作业环节,那么其成本将大大降低。
2.4 分站点
分站点的时效性决定了上线区域物流在运输调度上线路的优化和车辆的使用。不同时效性的分站点之间,路线优化和车辆的使用都会不相同。
2.5 运输网络
运输网络包括不限于由顶点(即区域物流分拣中心、客户)、无向边和有向弧组成的。根据货物属性的不同,采用不同的运输网络,所消耗的物流成本也不尽相同。
3 区域物流中的车辆调度模型分析
3.1 确立目标
对于区域物流而言,车辆从同一起讫点的运输问题,主要是指车辆从仓储中心出发访问一定数量的分站点后又回到原来的出发点的线路确定问题。其目标是寻求访问各点的次序,并使运行时间或距离最小化。
3.2 基本思路
采用节约算法求解的基本思路是:假设P是出发地点,A和B是要到达的地点,它们相互之间的道路距离分别是a,b,c。如果车辆从P分别到A和B地点,那么总里程为2 a+2b;如果车辆从P到A再到B,然后回到P,则总里程为a+b+c;两种方法的历程差是(2a+2b)-(a+b+c)=a+b-c,如果a+b-c>0,那么第二种方法将使总里程得到节约。
3.3 建立模型
根据上述基本思路,如果车辆需要到若干地点,那么就可以根据节约距离的大小顺序连接各点并规划出旅行路线。
结合上述基本思路,采用节约算法,如果a+b-c>0,那么第二种方法将使总里程得到节约。下面将其结合京东商城北京双树分拣中心区域物流车辆调配的实际问题进行分析。
京东商城北京双树分拣中心主要负责北京市各个区县的快件粗分拣,本文中我们以北京市丰台区的七个分站点配送站进行数学模型的演算分析。假设P为京东商城北京双树分拣中心所在地,A-G是P所负责粗分拣而后配送的京东商城北京市丰台区的七个分站点(A.丰台六号分站点;B.卢沟桥分站点;C.丰台一号分站点;D.世界公园分站点;E.云岗分站点;F.大红门分站点;G.南苑分站点)。结合京东商城北京双树分拣中心现状,每次可以利用的配送车辆是装载量3t的轻型“依维柯”,并限制车辆一次运行距离不超过150km。
在不采用任何方法的情况下,总里程数为PA、PB、PC、PD、PE、PF、PG的想加之和的2倍,即311×2=622 km
首先算出相互之间最短距离,根据仓储中心到各个分站点、分站点与分站点之间的距离,通过高德地图查询得知里程数,每个分站点的配送载重量由实际询问得知。进一步得出配送路线最短的距离矩阵,如表1所示。
根据最短距离矩阵图,计算出各用户之间的节约行程,如表2所示。
单位:km
单位:km
对节约行程按大小顺序进行排列,即B-E、D-E、B-D、A-E、A-D、C-E、A-B、C-D、B-C、D-G、A-C、D-F、E-G、E-F、B-F、B-G、F-G、A-F、C-F、A-G、C-G分别节约行程105km、96 km、94 km、81 km、79 km、79 km、77 km、77 km、76 km、76 km、72 km、72km、70 km、69 km、65 km、65 km、62 km、58 km、56 km、54 km、51 km。
按照节约行程顺序表,组合成配送路线图,并得出初始解,再根据其解得二次解。二次解按照节约行程的顺序大小,连接B-E、D-E、P-B、P-D,组成配送线路1。该路线装载量为2.8t,运行里程为135km,需要一辆3t货车。此时总配送路线5条,总运行距离278km,需要3t货车5辆。
据二次解求得最终解,按照节约行程顺序大小,A-E、C-E、A-B、C-D、B-C、D-G、D-F、B-F、B-G都有可能连接到二次解的配送线路1中,但是由于受到载重量和车辆每次行驶最大距离的限定,配送路线1不能再增加配送点,所以不再连接上述连接点。接下来按节约行程的顺序连接A-C、F-G、C-G、P-A、P-F,组成配送线路2,如下图所示。改配送路线装载量2.8 t,形成101 km,需要一辆3t轻型卡车。至此完成了全部配送路线的规划。总的配送路线共有两条,运行距离为236km,需要3t轻型卡车两辆。
最终解
有上述模型不难看出,采用节约算法求解,可以使总里程减少386km,也就是说,现有里程数仅占原先里程数的38%,按轻型卡车每公里成本1元计算,这样单纯的运输成本就可以节约62%,仅仅是丰台区一个区县的配送成本就可以节约这么多,那么北京市城六区及几个远郊区县的配送成本一下子就能下降一大截。这种区域物流对车辆进行的调配,不仅可以减少企业运输成本,也保证了客户体验不会下降,可谓一举两得。京东商城如果每次配送前都采用节约算法来进行区域车辆的调配,长期进行这项工作后,必然在配送成本上可以凌驾于领先的配送成本水平之上。
4 区域物流配送运输调度成本控制对策
4.1 区域物流合理规划
在配送作业中,合理计划对于区域物流分拣中心来说一定要做到位,不然就会出现以下几种情况,而这些情况会使配送成本增加。
4.1.1 区域物流的紧急配送
为了满足客户要求,提高客户体验,京东商城对自营商品进行“211”“311”限时达的服务,在区域物流的分拣中心可能需要安排正常配送之外的紧急配送。车辆的调度在紧急配送中很可能根本来不及,直接导致车辆空驶里程数增加,提高了快件的每公里物流成本。但实际上,在区域物流方面做出合理的应急预案准备,提前安排好车辆调度,依然可以很好地应对这种情况的发生。
京东商城在这方面便很有准备,它的优势在于资金和信息技术,虽然网点分布复杂,分站点时效性不能达到100%。但是通过后续各级分站点的配合,通过多次对线路的核查,并结合区域物流道路上的道路特点,与第三方物流的加盟并与之合作,在区域物流中搭建多频分站点。对于客户要求的突然要求或者其他紧急配送情况的产生,在车辆调度上,区域物流尽可能多地提高其装载率将客户需求均运送至分站点,借助区域快递的精密网点,分站点后续为广大消费者提供服务,满足个别用户的“紧急”需求。
4.1.2 区域物流的临时配送
区域物流的临时配送的出现情况,通常是在区域配送车辆调度之前未能对配送路线进行合理的规划或者运输方式选择不当而造成的。所以不得不另行安排车辆进行临时性配送,无形之间提高了运输成本。
在京东商城的日常经营中,他们尽可能地避免紧急配送和临时配送的情况发生以便更好地控制他们的配送成本。“311限时达”与“211限时达”的货物晚间均能准点抵达客户手中,以及在配送线路上的精心设计,都反映出京东商城对区域物流规划上的重视。规划好区域物流成本,就是对控制配送成本奠定了良好的基础。
4.2 分站点配送路线合理化
配送路线的设计不合理可能直接导致配送成本提高、配送速度下降、公司效益明显下滑等,因此,我们要对配送线路的合理化进行修改。通过最短路径法或者其他数学方法及经验的运用,结合实际的北京市道路周边状况进行安排,最终确定配送路线。但是值得注意的是,无论是什么样的方法,对其都有一定的约束条件,比如制定配送路线时要在政府部门允许的配送时间内进行等,不能违规操作,随心所欲。
4.3 车辆运输的合理性
无论是区域物流对车辆的调度还是分站点对电动三轮车的使用,都会因装货量不同,快递件的大小尺寸不同,在配送过程中使车辆的满载率不能充分使用。另外还有的客户可能一个人订了很多件不同品种的快件,其在配送过程中,不同的包装形态、不同的储存方式和不同的运输性质,导致车辆载货的过程中容易出现货损货差,也容易造成车辆装载率的浪费。为了避免车辆空间上的浪费,充分发挥车辆的装载效率,车辆调度都对此格外重视。货物密度较大的货物可能导致车辆载重量超过负荷,但又留有很大空间,造成资源浪费,较小密度的货物虽然能占满车辆的体积,可是不能达到满载载重量,也是一种资源浪费。最合理的装货方法是密度小的货物与密度大的货物进行混装,既能尽量占满空间,又达到了最大载重量,达到合理化装载并降低车辆运输成本,何乐而不为。同时也要对车辆进行必要的保养和维护,延长车辆的使用寿命,在保证运输安全的前提下,降低零件的更换频率。
5 结论
本文以控制区域物流车辆调度成本为主旨,首先叙述了区域物流车辆调度的相关概念及信息,并结合区域物流调度模型分析;最后对区域物流车辆调度的配送成本控制予以相应对策。期间,通过对京东商城分拣中心区域物流车辆调度模型的分拣,进而给予区域物流合理规划、分站点配送路线合理化、车辆运输合理化等决策。为了使区域物流中车辆调度成本最优化,无论是分拣中心的区域物流,还是分站点的“最后一公里”物流,都应秉承路线规划合理来进行,车辆的运输在于线路也在与人,业务人员素质的提高,更可以很好的爱惜车辆,完成作业,提高现代化物流信息系统的使用程度,最大限度地优化其调度配送成本。
参考文献
[1]吴隆杰.基于渔业生态足迹指数的渔业资源可持续利用测度研究[D].青岛:中国海洋大学,2006.
[2]陈作志,林昭进,邱永松.基于AHP的南海海域渔业资源可持续利用评价[J].自然资源学报,2010(2):249-257.
[3]陈力群,张朝晖,王宗灵.海洋渔业资源可持续利用的一种模式——海洋牧场[J].海岸工程,2006(4):71-76.
[4]张秀梅,王熙杰.山东省渔业资源增殖放流现状与展望[J].中国渔业经济,2009(2):51-59.
[5]张红智,张静.论我国的海洋产业结构及其优化[J].海洋科学进展,2005(2):243-247.
[6]陈新洲,徐冰,董振国,等.粮食安全需要“蓝色粮仓”[J].瞭望,2009(43):34-35.
[7]韩立民,李大海.“蓝色粮仓”:国家粮食安全的战略保障[J].农业经济问题,2015(1):24-29,110.
[8]卢昆,周娟枝,刘晓宁.蓝色粮仓的概念特征及其演化趋势[J].中国海洋大学学报:社会科学版,2012(2):35-39.
[9]韩立民,王金环.“蓝色粮仓”空间拓展策略选择及其保障措施[J].中国渔业经济,2013(2):53-58.
[10]孙立家.山东省“蓝色粮仓”建设的关联产业结构和布局优化研究[D].青岛:中国海洋大学,2013.
[11]黄丽惠.福建海洋经济强省建设的战略思考[J].湖北函授大学学报,2015(9):78-79,107.