收稿日期:20121018;修回日期:20121129 基金项目:国家自然科学基金重大项目(71132006)
作者简介:朱玲(1987),女,天津人,硕士,主要研究方向为物流供应链(zhuling1987@hotmail.com);吴迪(1954),男,辽宁沈阳人,教授,博
导,主要研究方向为运营与物流管理.
需求可拆分的汽车零部件循环取货路径优化研究
朱 玲,吴 迪
(上海交通大学 中美物流研究院,上海 200030)
摘 要:为了降低汽车零部件入厂物流的总成本,针对汽车零部件入厂物流的循环取货路径规划问题,提出将
供应商集货需求拆分配送的改进数学模型,以最小化运输和库存总成本为目标函数,并且满足时间窗和车辆容
量的限制。通过设计禁忌搜索算法求解,并根据模型的特点对初始解及邻域搜索方法进行改进。最后应用实验
数据验证算法有效性,并与其他算法对比,结果表明通过需求拆分可以节约运输成本并提高车辆装载率。
关键词:零部件入厂物流;循环取货;需求可拆分;时间窗;禁忌搜索算法
中图分类号:TP3016 文献标志码:A 文章编号:10013695(2013)06164705
doi
:10.3969/j.issn.10013695.2013.06.011
Researchonautomobilepartsmilkrunroutingwithsplitdeliveries
ZHULing,WUDi
(SinoUSGlobalLogisticsInstitute,ShanghaiJiaoTongUniversity,Shanghai200030,China)
Abstract:Themilkrunmodehasbeenwidelyusedintheautomobilepartssupply.Thekeytothemilkrunistoseektheop
timalpathsforthevehicles.Thispaperdevelopedamilkrunmodelwithtimewindowsandsplitdeliveries.Theobjectivefunc
tionwastominimizethetransportationandinventorycost.Inordertosolvethismodel
,thispaperproposedatabusearchalgo
rithm.Accordingtothespecificityofthemodel,itdesignedthetabusearchalgorithmwithspecialtreatmentsoninitialsolu
tionandneighborhoodsearch.Intheend,itusedsomecomputationalexperimentstotestifythevalidityandefficiencyofthe
modelandthealgorithm.Theresultsindicatethatthetransportationcostcanbesavedandthevehicleloadingratecanbeim
provedbythismodelandalgorithm.
Keywords:partssupplylogistics;milkrun;splitdeliveries;timewindows;tabusearchalgorithm
+
引言
准时生产方式(justintime,JIT)是由日本丰田汽车公司在
20世纪 50年代初提出,经 20几年逐步形成的一种先进生产
方式。其核心思想是消除浪费、降低成本,增加利益。而其中
浪费的主要原因是库存造成的。因此 JIT也可以说是一种追
求无库存或者最小库存的生产系统。
但是汽车制造厂一味地追求零库存而减小零部件供应的
订货批量,将会引起订货频次的增加,从而有可能导致高昂的
运输成本;相反,为了降低运输成本而减小订货频次、增加订货
批量,又将会导致库存成本的升高。这两者都将导致高昂的物
流总成本,不符合
JIT思想,为企业带来巨大浪费。因此,一种
以最小化库存和运输总成本为目标的循环取货模式得到了企
业和学者的广泛关注。
循环取货(
milkrun)是指汽车制造商用一辆货车从制造
厂或区域分拨中心(regionaldistributioncenter,RDC)出发,沿
事先设计好的路线,在每天固定的时间窗到指定的多个零部件
供应商处提取零部件,然后返回制造厂或区域分拨中心的供货
模式。这种 供货 模 式具 有 小批 量、多 频 次 以 及 准 时 性 的 特
点
[1]
,克服了供货批量与频次的矛盾。循环取货模式通常由
制造厂委托第三方物流(
thirdpartylogistics,TPL)来具体实施。
例如上海通用汽车与安吉天地物流合作,使得运输成本节约
30%,送货准时率、正确率都明显提高
[2]
。
循环取货模式应用的关键是取货路径的优化。文献[3]
设计了改进的启发式节约算法来求解
milkrun最优路径。文
献[1]提出了结合扫描法和禁忌搜索法的两阶段求解算法,将
车辆路径问题转换为多个旅行商问题,但是其在建立车辆路径
优化模型时,只考虑了运输成本作为目标函数,而没有考虑库
存成本。文献[4]引入了线边最大库存的限制,但是该模型限
定了每一家供应商只能由一条取货路径访问,这一限定虽然大
大降低了问题的复杂度,但是与现实情况并不相符;并且当一
家供应商的零部件可以被分配到多条路径中运输时,即需求可
拆分时,运输成本将会显著下降
[5]
,车辆装载率也将提高。文
献[6]建立了需求可拆分车辆路径问题的数学模型,并设计禁
忌搜索算法求解,但是该问题没有考虑时间窗的约束。文献
[7]提出了两阶段算法求解需求可拆分的车辆路径问题,但是
仅针对单车场、单车型且无时间窗约束。文献[
8]研究了需求
可拆分的开放车辆路径问题,即车辆最终不返回车场,因此也
不符合循环取货的要求。
由于目前尚没有研究针对带有时间窗约束的需求可拆分
的循环取货路径问题,因此本文将针对汽车零部件循环取货路
径优化问题,以需求可拆分为前提,建立以最小化运输和库存
总成本为目标函数,满足时间窗及容量约束的数学模型,并设
计改进禁忌搜索算法求解。
第 30卷第 6期
2013年 6月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol30No6
Jun2013