Title of article
Models foratravelingpurchaserproblemwithadditionalside-constraints
Author/Authors
Luis Gouveia، نويسنده , , AnaPaias ، نويسنده , , StefanVo? b، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
9
From page
550
To page
558
Abstract
The travelingpurchaserproblem(TPP)istheproblemofdeterminingatourofapurchaserthatneedsto
buy severalitemsindifferentshopssuchthatthetotalamountoftravelandpurchasecostsis
minimized.Motivatedbyanapplicationinmachinescheduling,westudyavariantoftheproblemwith
additionalconstraints,namely,alimitonthemaximumnumberofmarketstobevisited,alimitonthe
numberofitemsboughtpermarketandwhereonlyonecopyperitemneedstobebought.Wepresent
an integer linearprogramming (ILP) modelwhichisadequateforobtainingoptimalintegersolutionsfor
instanceswithupto100markets.WealsopresentandtestseveralvariationsofaLagrangianrelaxation
combinedwithasubgradientoptimizationprocedure.Therelaxedproblemcanbesolvedbydynamic
programmingandcanalsobeviewedasresultingfromapplyingastatespacerelaxationtechniquetoa
dynamicprogrammingformulation.TheLagrangianbasedmethodiscombinedwithaheuristicthat
attemptstotransformrelaxedsolutionsintofeasiblesolutions.Computationalresultsforinstances
with upto300marketsshowthatwiththeexceptionofafewcases,thereporteddifferencesbetween
best upperboundandlowerboundvaluesontheoptimalsolutionsarereasonablysmall.
Keywords
Traveling purchaser problem , Dynamic programming , State space relaxation , Discretized (time-dependent) formulation
Journal title
Computers and Operations Research
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927880
Link To Document