Optimization Online


The split-demand one-commodity pickup-and-delivery travelling salesman problem

Juan-Jose Salazar-Gonzalez(jjsalaza***at***ull.es)
Beatriz Santos-Hernández(besanher***at***ull.es)

Abstract: This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once,although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the problem with a single commodity flow formulation and design a branch-and-cut approach to solve it. We make use of Benders Decomposition to project out the flow variables from the formulation. Inequalities to strengthen the linear programming relaxation are also presented and separated within the approach. Extensive computational results illustrate the performance of the approach on benchmark instances from the literature.

Keywords: Vehicle Routing Problem; Branch and Cut; Split Demand.

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, June 2014.

Download: [PDF]

Entry Submitted: 06/20/2014
Entry Accepted: 06/20/2014
Entry Last Modified: 06/20/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society