A branch‐and‐cut algorithm for the preemptive swapping problem
Copyright policy )A branch‐and‐cut algorithm for the preemptive swapping problem
AbstractIn the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch‐and‐cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011
- HEC Montréal Canada
- University of Montreal Canada
Transportation, logistics and supply chain management, Applications of graph theory, Programming involving graphs or networks, swapping problem, precedence relationships, branch-and-cut, Deterministic network models in operations research, Polyhedral combinatorics, branch-and-bound, branch-and-cut, Boolean programming, vehicle routing
Transportation, logistics and supply chain management, Applications of graph theory, Programming involving graphs or networks, swapping problem, precedence relationships, branch-and-cut, Deterministic network models in operations research, Polyhedral combinatorics, branch-and-bound, branch-and-cut, Boolean programming, vehicle routing
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).18 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!