A constant-factor approximation algorithm for multi-vehicle collection for processing problem |
| |
Authors: | E Yücel F S Salman E L Örmeci E S Gel |
| |
Institution: | 1. College of Engineering, Ko? University, Istanbul, Turkey 2. School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, AZ, USA
|
| |
Abstract: | We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP( $C_{\max }$ )) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP( $C_{\max }$ ). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|