混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题

杨绍文; 钱斌; 胡蓉; 张梓琪

doi:10.12263/DZXB.20220908

您当前的位置：

首页 >

文章列表页 >

混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题

学术论文 | 更新时间：2025-12-11

- 混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题
- Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery
- 电子学报 2024年52卷第3期页码：909-923
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.云南省人工智能重点实验室，云南昆明 650500
- 作者简介：
  
  [ "杨绍文男，1995年出生，云南大理人，硕士研究生，目前研究方向为复杂系统智能优化. E-mail: yswkust@163.com" ]
  [ "钱斌男，1976年出生，云南曲靖人，教授，博士生导师，目前研究方向为智能调度理论与方法. E-mail: bin.qian@vip.163.com" ]
  [ "胡蓉女，1973年出生，贵州安顺人，副教授，硕士生导师，目前研究方向为优化方法与决策支持系统. E-mail: ronghu@vip.163.com" ]
  [ "张梓琪男，1989年出生，云南曲靖人，博士研究生，目前研究方向为智能算法与优化调度. Email:768894018@qq.com" ]
- 基金信息：
  
  国家自然科学基金(62173169;61963022);云南省基础研究重点项目(202201AS070030)
- DOI：10.12263/DZXB.20220908
  中图分类号： TP273
- 收稿：2022-08-01，
  
  修回：2023-02-18，
  
  纸质出版：2024-03-25
- 稿件说明：
移动端阅览
杨绍文,钱斌,胡蓉,等.混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题[J].电子学报,2024,52(03):909-923.

YANG Shao-wen, QIAN Bin, HU Rong, et al.Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery[J].Acta Electronica Sinica, 2024, 52(03): 909-923.
杨绍文,钱斌,胡蓉,等.混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题[J].电子学报,2024,52(03):909-923. DOI：10.12263/DZXB.20220908

YANG Shao-wen, QIAN Bin, HU Rong, et al.Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery[J].Acta Electronica Sinica, 2024, 52(03): 909-923. DOI：10.12263/DZXB.20220908

摘要

本文针对一类广泛存在的分布式加工装配和车辆配送集成调度问题（Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery，ISP_DPAVD），以最小化运输和延迟惩罚总成本为优化目标，提出一种混合三维分布估计算法（Hybrid three-Dimensional Estimation of Distribution Algorithm，H3DEDA）进行求解.ISP_DPAVD包含两个耦合的子问题，即加工装配阶段子问题（子问题1）和车辆配送阶段子问题（子问题2）.由于每个子问题1的解（部分解1）均会确定1个具体的子问题2，故ISP_DPAVD的解空间非常庞大.根据这一特点，在H3DEDA中，先设计结合邻域变换的启发式规则来快速获取子问题2的优良解，以实现子问题间的部分解耦并明显缩减搜索空间，再设计三维EDA引导的全局搜索和变邻域驱动的局部搜索来获取ISP_DPAVD的高质量解.通过在不同规模测试问题上的仿真实验和算法比较，验证了H3DEDA求解ISP_DPAVD的有效性.

Abstract

This paper proposes a hybrid three-dimensional distribution estimation algorithm (H3DEDA) to minimize the total cost of transportation and delay penalties for a kind of widely existed integrated scheduling problem (ISP_DPAVD)

which includes two coupled subproblems

i.e.

the subproblem in the production and assembly stage (subproblem 1) and the subproblem in the vehicle distribution stage (subproblem 2). Since each solution of subproblem 1 determines a specific subproblem 2

the solution space of the ISP_DPAVD is very large. According to this characteristic

in H3DEDA (Hybrid three-Dimensional Estimation of Distribution Algorithm)

the heuristic rules combined with neighborhood transformation are designed to quickly obtain the excellent solution of subproblem 2

so as to achieve partial decoupling between subproblems and significantly reduce the search space. Then

the global search guided by three-dimensional EDA and the local search driven by variable neighborhood operations are devised to acquire high-quality solution for the ISP_DPAVD. Simulation experiments and comparisons on the test problems with different scales verify the effectiveness of H3DEDA in solving ISP_DPAVD.

关键词

Keywords

references

XIONG F L , XING K Y . Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time [J ] . International Journal of Production Research , 2014 , 52 ( 9 ): 2743 - 2766 .

XIONG F L , XING K Y , WANG F , et al . Minimizing the total completion time in a distributed two stage assembly system with setup times [J ] . Computers & Operations Research , 2014 , 47 : 92 - 105 .

ZHANG G H , XING K Y . Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment [J ] . Computers & Industrial Engineering , 2018 , 125 : 423 - 433 .

LEI D M , SU B , LI M . Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling [J ] . International Journal of Production Research , 2021 , 59 ( 23 ): 7232 - 7245 .

陈雅玲 , 雷德明 . 求解分布式两阶段装配流水车间调度的帝国竞争协作算法 [J ] . 控制理论与应用 , 2021 , 38 ( 12 ): 1957 - 1967 .

CHEN Y L , LEI D M . An imperialist competition and cooperation algorithm for distributed two-stage assembly flow shop scheduling [J ] . Control Theory & Applications , 2021 , 38 ( 12 ): 1957 - 1967 . (in Chinese)

GHARAEI A , JOLAI F . A multi-agent approach to the integrated production scheduling and distribution problem in multi-factory supply chain [J ] . Applied Soft Computing , 2018 , 65 : 577 - 589 .

LI S , ZHONG X L , LI H , et al . Batch delivery scheduling with multiple decentralized manufacturers [J ] . Mathematical Problems in Engineering , 2014 , 2014 : 321513 .

YıLMAZ Ö F , PARDALOS P M . Minimizing average lead time for the coordinated scheduling problem in a two-stage supply chain with multiple customers and multiple manufacturers [J ] . Computers & Industrial Engineering , 2017 , 114 : 244 - 257 .

HAO J H , CAO L S , JIANG D K . Integrated production-distribution scheduling problem with multiple independent manufacturers [J ] . Mathematical Problems in Engineering , 2015 , 2015 : 579893 .

ABDOLLAHZADEH V , NAKHAIKAMALABADI I , HAJIMOLANA S M , et al . A multifactory integrated production and distribution scheduling problem with parallel machines and immediate shipments solved by improved whale optimization algorithm [J ] . Complexity , 2018 , 2018 : 5120640 .

MARANDI F , FATEMI GHOMI S M T . Integrated multi-factory production and distribution scheduling applying vehicle routing approach [J ] . International Journal of Production Research , 2019 , 57 ( 3 ): 722 - 748 .

QIN H , LI T , TENG Y , et al . Integrated production and distribution scheduling in distributed hybrid flow shops [J ] . Memetic Computing , 2021 , 13 ( 2 ): 185 - 202 .

HOU Y S , FU Y P , GAO K Z , et al . Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows [J ] . Expert Systems with Applications , 2022 , 187 : 115827 .

FU Y P , HOU Y S , CHEN Z H , et al . Modelling and scheduling integration of distributed production and distribution problems via black widow optimization [J ] . Swarm and Evolutionary Computation , 2022 , 68 : 101015 .

WANG S Y , WANG L . An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem [J ] . IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2016 , 46 ( 1 ): 139 - 149 .

周丰顺 , 胡蓉 , 钱斌 , 等 . 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题 [J ] . 电子学报 , 2021 , 49 ( 12 ): 2419 - 2427 .

ZHOU F S , HU R , QIAN B , et al . Hyper-heuristic three-dimensional estimation of distribution algorithm for solving distributed permutation flow-shop and vehicle transportation integrated scheduling problem [J ] . Acta Electronica Sinica , 2021 , 49 ( 12 ): 2419 - 2427 . (in Chinese)

郭晨 , 曾思豪 , 郭钧 , 等 . 混合分布估计算法求解模糊分布式装配柔性车间调度问题 [J ] . 系统工程理论与实践 , 2021 , 41 ( 4 ): 1037 - 1048 .

GUO C , ZENG S H , GUO J , et al . Hybrid estimation of distribution algorithm for distributed assembly flexible job shop scheduling problem with fuzzy processing time [J ] . Systems Engineering-Theory & Practice , 2021 , 41 ( 4 ): 1037 - 1048 . (in Chinese)

ZHANG Z Q , QIAN B , HU R , et al . A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem [J ] . Swarm and Evolutionary Computation , 2021 , 60 : 100785 .

POTTS C N , SEVAST'JANOV S V , STRUSEVICH V A , et al . The two-stage assembly scheduling problem: Complexity and approximation [J ] . Operations Research , 1995 , 43 ( 2 ): 346 - 355 .

AL-ANZI F S , ALLAHVERDI A . A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times [J ] . European Journal of Operational Research , 2007 , 182 ( 1 ): 80 - 94 .

BASIR S A , MAZDEH M M , NAMAKSHENAS M . Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system [J ] . Computers & Industrial Engineering , 2018 , 126 : 217 - 231 .

MONTGOMERY D C . Design and Analysis of Experiments [M ] . 6th ed . Hoboken : John Wiley & Sons , 2005 .

胡蓉 , 陈文博 , 钱斌 , 等 . 学习型蚁群算法求解绿色多车场车辆路径问题 [J ] . 系统仿真学报 , 2021 , 33 ( 9 ): 2095 - 2108 .

HU R , CHEN W B , QIAN B , et al . Learning ant colony algorithm for green multi-depot vehicle routing problem [J ] . Journal of System Simulation , 2021 , 33 ( 9 ): 2095 - 2108 . (in Chinese)

李正雯 , 胡蓉 , 钱斌 , 金怀平 , 吕阳 . 学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题 [J ] . 控制理论与应用 , 2023 , 40 ( 3 ): 549 - 557 .

LI Z W , HU R , QIAN B , et al . A learning discrete volleyball premier league algorithm for solving green two-echelon heterogeneous-fleet vehicle routing problem with time windows [J ] . Control Theory and Technology , 2023 , 40 ( 3 ): 549 - 557 . (in Chinese)

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题