实例介绍
【实例简介】
物流网络选址与路径优化问题的模型与启发式解法
120 交通运输工程学报 2006年 (i∈T) (10 表1小规模问题的计算结果 Tab. 1 Computation result of smalF-scaled problem (xh+xbk)-z≤1(i∈T,∈Ck∈K)(11) 最优解 ∈TUC (j∈C 问题规模 目标值 运行时间/s (12) NG= 3, NT=3, Nc= 8 3885 k≤s1(≤c1121=∑体k∈(13 NG=3,Nr=3,Nc=10 421.2 21 U-U+Nx≤N-1(i,∈S,k∈K)(14) NG=3,Nr=3,Nc=12 6850 580 ∈T NG=3,NT=3,Nc=14 8741 162000 注:Nc为供应商数量,Nr为配送中心数量,Nc为客户数量 ba≤B (g∈G) (16 用启发式算法求得初期解 xi∈/Q1 (i,j∈T∪C,k∈K)(17) l0;∈/0,1 ∈T (18 通过交换配送中心间的路径进行 第1次解的改善 ∈/O,1 ∈T,j∈C) (19) yk∈/0,1 (i∈C,k∈K) (20) 通过交换同一路径中客户的位置 (2-OPT法)进行第2次解的改善 式中:G为供应商的集合;T为配送中心的集合;C 为客户的集合;K为车辆的集合;Qk为车辆k的最 通过交换不同路径中的客户 进行第3次解的改善 大载质量:S为C的部分集合;C为从点到点j的 距离;B为供应商g的最大供应量;V为配送中心 SA模块 的最大货物通过量;D,为客户j的需求量;H2为 配送中心i的固定费用;L为从供应商g到配送中 是否满足终止条件 心i的单位运输费用;Fk为车辆k的固定费用;a为 解的输出 与通过量有关的系数;xk为对于车辆k,如果点i以 后的访问点是点j,即为1,否则为0;y为如果点j 图1基于SA的混合启发式算法 的货物由车辆k配送,即为1,否则为0;v;为如果 Fi Mixed heuristic algorit hm based on sa 使用配送中心i,即为1,否则为0;z为如果客户j传统启发式算法与智能启发式算法相结合的混合算 由配送中心提供服务,即为1,否则为0;pa为从供法,以期在短时间内求得全局最优解 应商g到配送中心的供应量。其中x、3计算分析 和pg为决策变量。 2问题的求解 为了对SA的参数进行设定,进行了预备实验 并确定参数如下:初始温度To为200冷却率α为 为了验证上述数学模型的正确性,用数理规划07,与温度相关的循环次数调整参数β为.1,最 商用软件 LINGO8.0对小规模问题进行了数值计大循环次数将按照问题规模的大小做适当的设定, 算,结果见表1。可以看出,随着问题的规模扩大,数据采用人工生成数据,在200km×200km的区 计算时间急剧增加;当客户达到14个时,计算时间域内随机生成指定个数的供应商、配送中心和客户, 长达45h,显然无法满足解决现实问题的需要。为并生成距离矩阵和客户需求量;采用C语言编程, 了满足解决现实问题的需要,有必要开发岀一种能计算结果见表2。从表2中的结果比较可以看出, 够在合理的时间内求得准最优解的近似算法。 表2最优解与近似解比较 传统启发式算法能够在短时间内求得局部最优 Tab 2 Comparison of optimal solution and approxi mate solution 解,但往往容易陷于局部最优,而无法求得全局最优 最优解 近似解 问题规模 解。智能启发式算法能够求得全局最优解,但计算时 目标值运行时间/s目标值运行时间/s% 间相对较长。如果能够将两者结合起来,既可以防止N=3N=3,Nc=8385 33965 求解过程陷于局部搜索无法跳出,保证全局解的搜3N=3NG=10+21221121 00 索,又可以缩短搜索时间达到在短时间内求得全局N-3-3Nc12|60s0620110 最优解的目的。基于上述考虑本文提出了图1的将ublishrigfoustAingnsestrvcu,trttp/www.urrhi.rct NG=3,Nr=3,Nc=1487411620008895 第3期 陈松岩,等:物流网络选址与路径优化问题的模型与启发式解法 121 本算法求得的近似解与 LINGO80计算的最优解心,再从配送中心到客户这一典型的物流过程,涉及 之间的误差很小,但计算时间却大大缩短了。依据运输与配送2个阶段和供应商、配送中心和客户3 结果虽然无法判定所提岀的混合启发式算法对于大个层次,提出了多供应商、多物流中心情况下的物流 规模问题的有效性,但可以看岀,对于求解小规模问路径与配送路径优化问题,给岀了问题的数学模型, 题是有效和良好的。对于大规模问题,将利用实例利用传统启发式算法与模拟退火法开发了混合近似 进行计算验证。 解法,通过人工生成数据和实例计算验证,可以看出 4应用实例 所提出的数学模型可以准确地描述此类问题,具有 良好的适应性,所提出的混合近似解法能够在短时 在应用实例中,将港口作为供应商来考虑,以进间内求解问题并得到接近于最优解的近似解,具有 口货物从港口经配送中心配送到客户过程中发生的较高的实用价值。但本模型没有考虑库存问题与供 费用最小化为目的,以港口的数量和位置、配送中心应商的成本问题,无法达到物流网络中各个环节的 数量和位置作为对象进行优化。实例的区域选择山整体优化,有待于今后进一步研究。 东省,候选港口为天津港、烟台港、威海港、青岛港 参考文献 日照港和连云港等6处,候选配送中心设置于山东 省除港口城市以外的13个地级市,设定客户分别位 References 于90个县(包括县级市)。为了分析候选港口和配1 I anen g Flpo C. Spatial de composit ion for a multI 送中心的数量及位置与目标值之间的关系,在计算 of Production Economics, 2000, 64(1/2/3): 177186 过程中,候选港口和配送中心的数量分别从1开始(21 Melkote s, Das kin m s. a n in te grated model of facil ity loca tion 增加(港口的位置为随机选择),计算结果见图2、3 and transportat ion netw ork design[ J. Transport ation Re search part A,2001,35(6):515538 6 [3] Goets chalckx M, Vidal C J Dogan K Modeling and design of global logistics s yst ems: a review of integrated strat e gic an d t act ical models and design algorithm s[ J European Journal of 0 05◇◇0◇◇◇◇◇◇◇ Operat ional Research, 2002, 143 (1):118 135791113 [4] H wang H S Design of suppl y chain logist ics sy stem con sider- 港口数量 配送中心数量 ing service level[ J. Computers and Industrial Engineerin g, 图2港口数量与 图3配送中心数量与 2002,43(1/2):283297 目标函数值关系 目标函数值关系 [5] WuT H, Low C, Bai J W. Heurist ic s ol ution s to mu ltt depot Fig2 Relation of ob ject value Fig 3 Relation of ob ject value locatioN rou tin g pr ob lems[ J]. Computers and Operations Re- and ports number and changing depots num be search,2002,29(10):13931415 可以看出,随着候选港口数量的增加.目标值呈[6 Syam ss. A model and met hodologies for the locat ion p rob lem 下降趋势,说明可供选择的港口越多,求得最优解的 with logist ical components[ J]. Computers and Operations Re 机会越大,但本例中,当候选港口的数量增加到5个 se arch,200)2,29(9):l173-1193 时,目标值达到最小(实际被选中的港口为3个);候 [7 Amiri A. Designing a distribution network in a suppl y chain system[ J]. European Jou rnal of O perat ional Research, 2004 选配送中心数量的变化也呈相同的趋势,当候选配 171(2):567576 送中心数量达到9个时,目标值达到最小(实际被选8 G ena m, Syarif a. Hybrid genetic algorit hm for mult+ time pe- 中的配送中心为8个);本实例的计算时间都在8s riod production/ distribution planning[ J1. Computers and Ir 以内,虽然无法判断所求解为最优解,但从计算结果 dustrial Engineering, 2005, 48(4): 799809 来看,基本接近最优,因此可以认为本算法对于求解9工丰元,潘福全张丽霞等基于交通限制的路网最优路径算 大规模问题也是有效和良好的 法J.交通运输工程学报,2005,5(1):9295 Wang Feng yuan, Pan Fuquan, Zhang Li xia, et al. Opti mal 5结语 path algorithm of road netw ork with traffic rest riction[ JI Journ al of Traffic and Trans port ation Engin eering, 2005, 5(1) 本文将研究范围界定在商品从供应商到配送中 9295.(in Ch inese o1994-2012ChinaacAdemicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 【实例截图】
【核心代码】
物流网络选址与路径优化问题的模型与启发式解法
120 交通运输工程学报 2006年 (i∈T) (10 表1小规模问题的计算结果 Tab. 1 Computation result of smalF-scaled problem (xh+xbk)-z≤1(i∈T,∈Ck∈K)(11) 最优解 ∈TUC (j∈C 问题规模 目标值 运行时间/s (12) NG= 3, NT=3, Nc= 8 3885 k≤s1(≤c1121=∑体k∈(13 NG=3,Nr=3,Nc=10 421.2 21 U-U+Nx≤N-1(i,∈S,k∈K)(14) NG=3,Nr=3,Nc=12 6850 580 ∈T NG=3,NT=3,Nc=14 8741 162000 注:Nc为供应商数量,Nr为配送中心数量,Nc为客户数量 ba≤B (g∈G) (16 用启发式算法求得初期解 xi∈/Q1 (i,j∈T∪C,k∈K)(17) l0;∈/0,1 ∈T (18 通过交换配送中心间的路径进行 第1次解的改善 ∈/O,1 ∈T,j∈C) (19) yk∈/0,1 (i∈C,k∈K) (20) 通过交换同一路径中客户的位置 (2-OPT法)进行第2次解的改善 式中:G为供应商的集合;T为配送中心的集合;C 为客户的集合;K为车辆的集合;Qk为车辆k的最 通过交换不同路径中的客户 进行第3次解的改善 大载质量:S为C的部分集合;C为从点到点j的 距离;B为供应商g的最大供应量;V为配送中心 SA模块 的最大货物通过量;D,为客户j的需求量;H2为 配送中心i的固定费用;L为从供应商g到配送中 是否满足终止条件 心i的单位运输费用;Fk为车辆k的固定费用;a为 解的输出 与通过量有关的系数;xk为对于车辆k,如果点i以 后的访问点是点j,即为1,否则为0;y为如果点j 图1基于SA的混合启发式算法 的货物由车辆k配送,即为1,否则为0;v;为如果 Fi Mixed heuristic algorit hm based on sa 使用配送中心i,即为1,否则为0;z为如果客户j传统启发式算法与智能启发式算法相结合的混合算 由配送中心提供服务,即为1,否则为0;pa为从供法,以期在短时间内求得全局最优解 应商g到配送中心的供应量。其中x、3计算分析 和pg为决策变量。 2问题的求解 为了对SA的参数进行设定,进行了预备实验 并确定参数如下:初始温度To为200冷却率α为 为了验证上述数学模型的正确性,用数理规划07,与温度相关的循环次数调整参数β为.1,最 商用软件 LINGO8.0对小规模问题进行了数值计大循环次数将按照问题规模的大小做适当的设定, 算,结果见表1。可以看出,随着问题的规模扩大,数据采用人工生成数据,在200km×200km的区 计算时间急剧增加;当客户达到14个时,计算时间域内随机生成指定个数的供应商、配送中心和客户, 长达45h,显然无法满足解决现实问题的需要。为并生成距离矩阵和客户需求量;采用C语言编程, 了满足解决现实问题的需要,有必要开发岀一种能计算结果见表2。从表2中的结果比较可以看出, 够在合理的时间内求得准最优解的近似算法。 表2最优解与近似解比较 传统启发式算法能够在短时间内求得局部最优 Tab 2 Comparison of optimal solution and approxi mate solution 解,但往往容易陷于局部最优,而无法求得全局最优 最优解 近似解 问题规模 解。智能启发式算法能够求得全局最优解,但计算时 目标值运行时间/s目标值运行时间/s% 间相对较长。如果能够将两者结合起来,既可以防止N=3N=3,Nc=8385 33965 求解过程陷于局部搜索无法跳出,保证全局解的搜3N=3NG=10+21221121 00 索,又可以缩短搜索时间达到在短时间内求得全局N-3-3Nc12|60s0620110 最优解的目的。基于上述考虑本文提出了图1的将ublishrigfoustAingnsestrvcu,trttp/www.urrhi.rct NG=3,Nr=3,Nc=1487411620008895 第3期 陈松岩,等:物流网络选址与路径优化问题的模型与启发式解法 121 本算法求得的近似解与 LINGO80计算的最优解心,再从配送中心到客户这一典型的物流过程,涉及 之间的误差很小,但计算时间却大大缩短了。依据运输与配送2个阶段和供应商、配送中心和客户3 结果虽然无法判定所提岀的混合启发式算法对于大个层次,提出了多供应商、多物流中心情况下的物流 规模问题的有效性,但可以看岀,对于求解小规模问路径与配送路径优化问题,给岀了问题的数学模型, 题是有效和良好的。对于大规模问题,将利用实例利用传统启发式算法与模拟退火法开发了混合近似 进行计算验证。 解法,通过人工生成数据和实例计算验证,可以看出 4应用实例 所提出的数学模型可以准确地描述此类问题,具有 良好的适应性,所提出的混合近似解法能够在短时 在应用实例中,将港口作为供应商来考虑,以进间内求解问题并得到接近于最优解的近似解,具有 口货物从港口经配送中心配送到客户过程中发生的较高的实用价值。但本模型没有考虑库存问题与供 费用最小化为目的,以港口的数量和位置、配送中心应商的成本问题,无法达到物流网络中各个环节的 数量和位置作为对象进行优化。实例的区域选择山整体优化,有待于今后进一步研究。 东省,候选港口为天津港、烟台港、威海港、青岛港 参考文献 日照港和连云港等6处,候选配送中心设置于山东 省除港口城市以外的13个地级市,设定客户分别位 References 于90个县(包括县级市)。为了分析候选港口和配1 I anen g Flpo C. Spatial de composit ion for a multI 送中心的数量及位置与目标值之间的关系,在计算 of Production Economics, 2000, 64(1/2/3): 177186 过程中,候选港口和配送中心的数量分别从1开始(21 Melkote s, Das kin m s. a n in te grated model of facil ity loca tion 增加(港口的位置为随机选择),计算结果见图2、3 and transportat ion netw ork design[ J. Transport ation Re search part A,2001,35(6):515538 6 [3] Goets chalckx M, Vidal C J Dogan K Modeling and design of global logistics s yst ems: a review of integrated strat e gic an d t act ical models and design algorithm s[ J European Journal of 0 05◇◇0◇◇◇◇◇◇◇ Operat ional Research, 2002, 143 (1):118 135791113 [4] H wang H S Design of suppl y chain logist ics sy stem con sider- 港口数量 配送中心数量 ing service level[ J. Computers and Industrial Engineerin g, 图2港口数量与 图3配送中心数量与 2002,43(1/2):283297 目标函数值关系 目标函数值关系 [5] WuT H, Low C, Bai J W. Heurist ic s ol ution s to mu ltt depot Fig2 Relation of ob ject value Fig 3 Relation of ob ject value locatioN rou tin g pr ob lems[ J]. Computers and Operations Re- and ports number and changing depots num be search,2002,29(10):13931415 可以看出,随着候选港口数量的增加.目标值呈[6 Syam ss. A model and met hodologies for the locat ion p rob lem 下降趋势,说明可供选择的港口越多,求得最优解的 with logist ical components[ J]. Computers and Operations Re 机会越大,但本例中,当候选港口的数量增加到5个 se arch,200)2,29(9):l173-1193 时,目标值达到最小(实际被选中的港口为3个);候 [7 Amiri A. Designing a distribution network in a suppl y chain system[ J]. European Jou rnal of O perat ional Research, 2004 选配送中心数量的变化也呈相同的趋势,当候选配 171(2):567576 送中心数量达到9个时,目标值达到最小(实际被选8 G ena m, Syarif a. Hybrid genetic algorit hm for mult+ time pe- 中的配送中心为8个);本实例的计算时间都在8s riod production/ distribution planning[ J1. Computers and Ir 以内,虽然无法判断所求解为最优解,但从计算结果 dustrial Engineering, 2005, 48(4): 799809 来看,基本接近最优,因此可以认为本算法对于求解9工丰元,潘福全张丽霞等基于交通限制的路网最优路径算 大规模问题也是有效和良好的 法J.交通运输工程学报,2005,5(1):9295 Wang Feng yuan, Pan Fuquan, Zhang Li xia, et al. Opti mal 5结语 path algorithm of road netw ork with traffic rest riction[ JI Journ al of Traffic and Trans port ation Engin eering, 2005, 5(1) 本文将研究范围界定在商品从供应商到配送中 9295.(in Ch inese o1994-2012ChinaacAdemicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论