Publication:
A constant-factor approximation algorithm for multi-vehicle collection for processing problem

dc.contributor.coauthorGel, Esma S.
dc.contributor.departmentDepartment of Industrial Engineering
dc.contributor.departmentGraduate School of Sciences and Engineering
dc.contributor.kuauthorÖrmeci, Lerzan
dc.contributor.kuauthorSalman, Fatma Sibel
dc.contributor.kuauthorYücel, Eda
dc.contributor.schoolcollegeinstituteCollege of Engineering
dc.contributor.schoolcollegeinstituteGRADUATE SCHOOL OF SCIENCES AND ENGINEERING
dc.date.accessioned2024-11-09T23:20:17Z
dc.date.issued2013
dc.description.abstractWe 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()) 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(). 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.
dc.description.indexedbyWOS
dc.description.indexedbyScopus
dc.description.issue7
dc.description.openaccessNO
dc.description.sponsoredbyTubitakEuN/A
dc.description.volume7
dc.identifier.doi10.1007/s11590-012-0578-1
dc.identifier.issn1862-4472
dc.identifier.scopus2-s2.0-84884669819
dc.identifier.urihttps://doi.org/10.1007/s11590-012-0578-1
dc.identifier.urihttps://hdl.handle.net/20.500.14288/10677
dc.identifier.wos324824600017
dc.keywordsApproximation algorithm
dc.keywordsVehicle routing and scheduling
dc.keywordsMakespan
dc.language.isoeng
dc.publisherSpringer Heidelberg
dc.relation.ispartofOptimization Letters
dc.subjectOperations research
dc.subjectManagement science
dc.subjectMathematics
dc.titleA constant-factor approximation algorithm for multi-vehicle collection for processing problem
dc.typeJournal Article
dspace.entity.typePublication
local.contributor.kuauthorYücel, Eda
local.contributor.kuauthorSalman, Fatma Sibel
local.contributor.kuauthorÖrmeci, Lerzan
local.publication.orgunit1GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
local.publication.orgunit1College of Engineering
local.publication.orgunit2Department of Industrial Engineering
local.publication.orgunit2Graduate School of Sciences and Engineering
relation.isOrgUnitOfPublicationd6d00f52-d22d-4653-99e7-863efcd47b4a
relation.isOrgUnitOfPublication3fc31c89-e803-4eb1-af6b-6258bc42c3d8
relation.isOrgUnitOfPublication.latestForDiscoveryd6d00f52-d22d-4653-99e7-863efcd47b4a
relation.isParentOrgUnitOfPublication8e756b23-2d4a-4ce8-b1b3-62c794a8c164
relation.isParentOrgUnitOfPublication434c9663-2b11-4e66-9399-c863e2ebae43
relation.isParentOrgUnitOfPublication.latestForDiscovery8e756b23-2d4a-4ce8-b1b3-62c794a8c164

Files