Title
Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arc routing with soft time windows Solving the mobile mapping van problem: a hybrid metaheuristic for capacitated arc routing with soft time windows
Author
Faculty/Department
Faculty of Applied Economics
Publication type
article
Publication
New York, N.Y. ,
Subject
Engineering sciences. Technology
Computer. Automation
Source (journal)
Computers & operations research. - New York, N.Y.
Volume/pages
37(2010) :11 , p. 1873-1876
ISSN
0305-0548
ISI
000278504000006
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
Creating digital maps often requires driving around the streets in a so-called mapping van. Tele Atlas, the world leading supplier of maps and map data, uses a fleet of such vehicles to take pictures of streets and road signs. Minimising the number of days that a vehicle needs to traverse all streets in a given region gives rise to a capacitated arc routing problem. A specific characteristic of this problem, however, is the fact that taking pictures in the direction of the sun should be avoided as much as possible. This requirement adds soft time windows to the problem. In this paper we solve the mobile mapping van problem by transforming it into a vehicle routing problem with soft time windows. We then apply a hybrid metaheuristic, consisting of a local search phase to decrease the number of days and an iterated local search phase to minimise the time window violations. An exact linear programming solver is embedded to calculate the ideal starting time of the vehicle in each street. Our method is tested on academic and real-life problem instances and shown to be effective.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000278504000006&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000278504000006&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000278504000006&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle