Browsing by Author "Vigo, D."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Placeholder
    ArticlePublicationMetadata only
    Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs
    (Elsevier, 2012-05) Erdoğan, Güneş; Battarra, M.; Laporte, G.; Vigo, D.; Industrial Engineering; ERDOĞAN, Güneş
    This paper studies the Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs. The subproblem of minimizing the handling cost for a fixed route is analyzed in detail. It is solved by means of an exact dynamic programming algorithm with quadratic complexity and by an approximate linear time algorithm. Three metaheuristics integrating these solution methods are developed. These are based on tabu search, iterated local search and iterated tabu search. The three heuristics are tested and compared on instances adapted from the related literature. The results show that the combination of tabu search and exact dynamic programming performs the best, but using the approximate linear time algorithm considerably decreases the CPU time at the cost of slightly worse solutions.
  • Placeholder
    ArticlePublicationMetadata only
    The traveling salesman problem with pickups, deliveries, and handling costs
    (Informs, 2010-08) Battarra, M.; Erdoğan, Güneş; Laporte, G.; Vigo, D.; Industrial Engineering; ERDOĞAN, Güneş
    This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cutalgorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.