列生成
自动引导车
计算机科学
布线(电子设计自动化)
光学(聚焦)
数学优化
作业车间调度
路径(计算)
车辆路径问题
最短路径问题
栏(排版)
分布式计算
数学
理论计算机科学
人工智能
嵌入式系统
计算机网络
帧(网络)
物理
图形
光学
作者
Nirup Krishnamurthy,Rajan Batta,Mark H. Karwan
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:1993-12-01
卷期号:41 (6): 1077-1090
被引量:146
标识
DOI:10.1287/opre.41.6.1077
摘要
Automated guided vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. This paper details solution methodologies for the static routing problem in which demand assignment of the AGVs are known; the focus is to obtain an implementable solution within a reasonable amount of computer time. The objective is to minimize the makespan, while routing AGVs on a bidirectional network in a conflict-free manner. This problem is solved via column generation. The master problem in this column generation procedure has the makespan and vehicle interference constraints. Columns in the master problem are routes iteratively generated for each AGV. The subproblem is a constrained shortest path problem with time-dependent costs on the edges. An improvement procedure is developed to better the solution obtained at the end of the master-subproblem interactions. Several methods of iterating between the master and subproblem are experimented with in-depth computational experiments. Our empirical results indicate that the procedure as a whole usually generates solutions that are within a few percent of a proposed bound, within reasonable computer time.
科研通智能强力驱动
Strongly Powered by AbleSci AI