Publication:
Capacitated arc routing problem with deadheading demands

dc.contributor.coauthorSipahioglu, Aydin
dc.contributor.departmentN/A
dc.contributor.kuauthorKirlik, Gökhan
dc.contributor.kuprofilePhD Student
dc.contributor.schoolcollegeinstituteGraduate School of Sciences and Engineering
dc.contributor.yokidN/A
dc.date.accessioned2024-11-09T23:29:38Z
dc.date.issued2012
dc.description.abstractCapacitated arc routing problem (CARP) is the determination of vehicle tours that serve all positive-demand edges (required edge) exactly once without exceeding vehicle capacity while minimizing sum of all tour costs. In CARP, total demand of a tour is calculated by means of all required edges on the tour. In this study, a new CARP variation is introduced, which considers not only required edges but also traversed edges while calculating total demand of the tour. The traversing demand occurs when the traversed edge is either servicing or non-servicing (deadheading). Since the new CARP formulation incurs deadheading edge demands it is called CARP with deadheading demands. An integer linear model is given for the problem which is used to solve small-sized instances, optimally. A constructive heuristic is presented to solve the problem which is a modified version of a well-known CARP heuristic. Furthermore, two post-optimization procedures are presented to improve the solution of the heuristic algorithm. The effectiveness of the proposed methods is shown on test problems, which are obtained by modifying CARP test instances.
dc.description.indexedbyWoS
dc.description.indexedbyScopus
dc.description.issue10
dc.description.openaccessNO
dc.description.publisherscopeInternational
dc.description.volume39
dc.identifier.doi10.1016/j.cor.2011.12.008
dc.identifier.eissn1873-765X
dc.identifier.issn0305-0548
dc.identifier.scopus2-s2.0-84856121276
dc.identifier.urihttp://dx.doi.org/10.1016/j.cor.2011.12.008
dc.identifier.urihttps://hdl.handle.net/20.500.14288/12085
dc.identifier.wos301313900011
dc.keywordsCapacitated arc routing problem
dc.keywordsDeadheading edge demands
dc.keywordsMathematical model
dc.keywordsConstructive heuristic
dc.keywordsPost-optimization procedure
dc.keywordsSensor-based coverage
dc.keywordsApproximation algorithms
dc.keywordsSearch
dc.languageEnglish
dc.publisherPergamon-Elsevier Science Ltd
dc.sourceComputers & Operations Research
dc.subjectComputer science
dc.subjectEngineering
dc.subjectIndustrial engineering
dc.subjectOperations research
dc.subjectManagement science
dc.titleCapacitated arc routing problem with deadheading demands
dc.typeJournal Article
dspace.entity.typePublication
local.contributor.authorid0000-0002-3823-908X
local.contributor.kuauthorKirlik, Gökhan

Files