跨单元调度及其车辆路径集成优化

doi:10.3969/j.issn.1004-132X.2022.06.014

中国机械工程 ›› 2022, Vol. 33 ›› Issue (06): 747-755.DOI: 10.3969/j.issn.1004-132X.2022.06.014

跨单元调度及其车辆路径集成优化

连永伟1;董钊睿1，2;刘琼1

1.华中科技大学机械科学与工程学院，武汉，430074
2.昆山市科学技术局，昆山，215316

出版日期:2022-03-25 发布日期:2022-04-21
通讯作者: 刘琼（通信作者），女，1965生，教授。研究方向为制造系统集成优化、物流与供应链管理等。E-mail：qiongliu@hust.edu.cn。
作者简介:连永伟，男，1996年生，硕士研究生。研究方向为跨单元调度与车辆路径集成优化。E-mail：M202070707@hust.edu.cn。

Integrated Optimization of Intercell Scheduling and Vehicle Routing

LIAN Yongwei1;DONG Zhaorui1，2;LIU Qiong1

1.School of Mechanical Science and Engineering，Huazhong University of Science and Technology，Wuhan，430074
2.Kunshan Science and Technology Bureau，Kunshan，Jiangsu，215316

Online:2022-03-25 Published:2022-04-21

摘要/Abstract

摘要： 为了提高跨单元调度中车辆利用率，降低运输成本和缩短完工时间，综合考虑调度方案中零件的加工顺序和异常件运输路径之间的相互影响，建立了一个以最小化最大完成时间和总成本为优化目标的跨单元调度及其车辆路径集成优化模型。提出了一种包含工序编码、机器编码、单元编码、车辆编码和车辆路径编码的五段式编码方法；设计了基于分解的多目标进化算法，针对算法迭代过程中可能产生不可行解的问题，提出了一种基于二叉树的车辆路径调整方法以及车辆载荷调整方法。通过实例分析，并将集成优化结果与常见运输策略结果、车辆共享策略结果进行了对比，集成优化模型在缩短最小完工时间和降低总成本方面可获得更优的结果，从而验证了所提集成优化模型的有效性。

关键词: 单元制造, 跨单元调度, 车辆路径问题, 基于分解的多目标进化算法

Abstract: In order to improve utilization rates of vehicles， reduce makespan and total costs， an integrated optimization model of intercell scheduling and the vehicle routing was established to minimize makespan and total costs. Interrelationships between processing sequences of parts and transportation routes of exceptional parts were considered. A five-segment coding method including operation， machine， cell， vehicle and vehicle route was proposed. A MOEA/D was designed. To ensure feasible solutions in iterative processes of the algorithm， a binary tree based adjustment method and a vehicle capacity constraint adjustment method were proposed. The proposed model was verified through a case study. Results were compared to those of a common transportation strategy and a vehicle sharing strategy. The proposed integrated optimization model may yield better results on both makespan and total costs.

Key words: cellular manufacturing, intercell scheduling, vehicle routing problem, multi-objective evolutionary algorithm based on decomposition（MOEA/D）

中图分类号:

TP391

连永伟, 董钊睿, 刘琼. 跨单元调度及其车辆路径集成优化[J]. 中国机械工程, 2022, 33(06): 747-755.

LIAN Yongwei, DONG Zhaorui, LIU Qiong. Integrated Optimization of Intercell Scheduling and Vehicle Routing[J]. China Mechanical Engineering, 2022, 33(06): 747-755.

参考文献

［1］SHAFER S M， CHARNES J M. A Simulation Ana-lyses of Factors Influencing Loading Practices in Cellular Manufacturing［J］. International Journal of Production Research， 1995， 33（1）：279-290.
［2］ZENG C， TANG J， YAN C. Job-shop Cell-scheduling Problem with Inter-cell Moves and Automated Guided Vehicles［J］. Journal of Intelligent Manufacturing， 2014， 26（5）：1-15.
［3］田云娜，李冬妮，刘兆赫，等. 一种基于动态决策块的超启发式跨单元调度方法［J］. 自动化学报， 2016， 42（4）：524-534.
TIAN Yunna， LI Dongni， LIU Zhaohe， et al. A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling［J］. Journal of Automatica Sinica， 2016， 42（4）：524-534.
［4］刘兆赫，李冬妮，王乐衡，等. 考虑运输能力限制的跨单元调度方法［J］. 自动化学报， 2015， 41（5）：885-898.
LIU Zhaohe， LI Dongni， WANG Leheng， et al. An Inter-cell Scheduling Approach Considering Transportation Capacity Constraints［J］. Journal of Automatica Sinica， 2015， 41（5）：885-898.
［5］李冬妮，贾晓宇，陈琳，等. 基于蚁群算法和遗传规划的跨单元调度方法［J］. 北京理工大学学报， 2017， 37（7）：704-710.
LI Dongni， JIA Xiaoyu， CHEN Lin， et al. Intercell Scheduling Approach Based on Ant Colony Optimization Algorithm and Genetic Programming［J］. Transactions of Beijing Institute of Technology， 2017， 37（7）：704-710.
［6］贾凌云，李冬妮，田云娜. 基于混合蛙跳和遗传规划的跨单元调度方法［J］. 自动化学报， 2015， 41（5）：936-948.
JIA Lingyun， LI Dongni， TIAN Yunna， et al. An Intercell Scheduling Approach Using Shuffled Frog Leaping Algorithm and Genetic Programming［J］. Journal of Automatica Sinica， 2015， 41（5）：936-948.
［7］梅旭. 基于运输车辆共享策略的跨单元调度优化研究［D］. 武汉：华中科技大学， 2019.
MEI Xu. Research on Inter-cell Scheduling Optimization Based on Transportation Vehicle Sharing Strategy［D］. Wuhan：Huazhong University of Science and Technology， 2019.
［8］DANLOUP N， ALLAOUI H， GONCALVES G. A Comparison of Two Meta-heuristics for The Pickup and Delivery Problem with Transshipment［J］. Computers & Operations Research， 2018， 100：155-171.
［9］VELASCO N， CASTAGLIOLA P， DEJAX P， et al. A Memetic Algorithm for a Pick-up and Delivery Problem by Helicopter［M］∥ Bio-inspired Algorithms for the Vehicle Routing Problem. Berlin：Springer， 2008：173-190.
［10］LU Q， DESSOUKY M. An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem［J］. Transportation Science， 2004， 38（4）：503-514.
［11］TSENG H E. Guided Genetic Algorithms for Solving a Larger Constraint Assembly Problem［J］. International Journal of Production Research， 2006， 44（3）：601-625.
［12］张超勇，董星，王晓娟，等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度［J］. 机械工程学报， 2010， 46（11）：156-164.
ZHANG Chaoyong， DONG Xing， WANG Xiaojuan， et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem［J］. Journal of Mechanical Engineering， 2010， 46（11）：156-164.
［13］GEVIN V， TRI S， DYAH E H， et al. Image Clustering Using Genetic Algorithm with Tournament Selection and Uniform crossover［J］. IOP Conference Series：Materials Science and Engineering， 2020， 852（1）：012043.
［14］ZHANG Q， LI H. MOEA/D：A Multi-objective Evolutionary Algorithm Based on Decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）：712-731.

[1]	辜勇, 袁源乙, 张列, 段晶晶. 带时间窗的多中心半开放式车辆路径问题[J]. 中国机械工程, 2020, 31(14): 1733-1740.
[2]	周蓉, 沈维蕾. [供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法[J]. 中国机械工程, 2018, 29(22): 2740-2749.
[3]	陈呈频;韩胜军;鲁建厦;陈青丰;王成. 多车场与多车型车辆路径问题的多染色体遗传算法[J]. 中国机械工程, 2018, 29(02): 218-223.
[4]	周蓉, 沈维蕾, 刘明周, 赵韩. 带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法[J]. 中国机械工程, 2016, 27(04): 494-502.
[5]	张志峰;谢奉军;肖人彬;. 基于状态熵模型的单元制造系统复杂性研究[J]. J4, 2009, 20(19): 0-2274.
[6]	陈美军;张志胜;史金飞;. 多约束下多车场车辆路径问题的蚁群算法研究[J]. J4, 2008, 19(16): 0-2015.

跨单元调度及其车辆路径集成优化

Integrated Optimization of Intercell Scheduling and Vehicle Routing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics