9. Travelling Salesman Problems with constraints: the TSP with time windows

The third part of this manual deals with Routing Problems: we have a graph[1] and seek to find a set of routes covering some or all nodes and/or edges/arcs while optimizing an objective function along the routes[2] (time, vehicle costs, etc.) and respecting certain constraints (number of vehicles, goods to pickup and deliver, fixed depots, capacities, clients to serve, time windows, etc.).

[1]A graph G=(V,E) is a set of vertices (the set V) connected by edges (the set E). A directed edge is called an arc. When we have capacities on the edges, we talk about a network.
[2]The transportation metaphor is helpful to visualize the problems but the class of Routing Problems is much broader. The Transportation Problem for instance is really an Assignment Problem. Networks can be of any type: telephone networks (circuit switching), electronic data networks (such as the internet), VLSI (the design of chips), etc.

To solve these problems, the or-tools offers a dedicated Constraint Programming sub-library: the Routing Library (RL).

The next two chapters each deal with one of two broad categories of Routing Problems:

These three categories of problems share common properties but they all have their own paradigms and scientific communities.

In this chapter, we’ll discover the RL with what is probably the most studied problem in Operations Research: the Travelling Salesman Problem (TSP)[3].

[3]We use the Canadian (and British, and South African, and...) spelling of the verb travelling but you’ll find much more scientific articles under the American spelling: traveling.

We use the excellent C++ ePiX library[4] to visualize TSP solutions in TSPLIB format and TSPTW solutions in López-Ibáñez-Blum and da Silva-Urrutia formats.

[4]The ePiX library uses the \text{\TeX/\LaTeX} engine to create beautiful graphics.

Overview:

We start this chapter by presenting in broad terms the different categories of Routing Problems and describe the Routing Library (RL) in a nutshell. Next, we introduce the Travelling Salesman Problem (TSP) and the TSPLIB instances. To better understand the RL, we say a few words about its inner working and the CP model we use. Because most of the Routing Problems are intractable, we use Local Search. We explain our two phases approach in details and show how to model the TSP in a few lines. Finally, we model and solve the TSP with Time Windows.

Prerequisites:

Files:

You can find the code in the directory documentation/tutorials/cplusplus/chap9.

The files inside this directory are:

  • tsp.h: This file contains the TSPData class that records the data for the TSP. This file is used throughout the TSP examples.
  • tsplib.h: Declarations of TSPLIB keywords and the TSPLIBDistanceFunctions class.
  • tsp_epix.h: This file provides the helper functions to visualize TSPLIB solutions with the ePiX library.
  • tsplib_solution_to_epix.cc: A simple program to visualize solutions in TSPLIB format with the ePiX library.
  • tsp_minimal.cc: A minimalist implementation of the TSP with the RL.
  • tsp.cc: A basic implementation of the TSP with the RL.
  • tsp_forbidden_arcs.cc: The TSP with forbidden arcs between some nodes.
  • tsptw.h: This file contains the TSPTWData class that records the data for the Travelling Salesman Problem with Time Windows. This file is used throughout the TSPTW examples.
  • tsptw_epix.h: This file provides the helper functions to visualize TSPTW solutions with the ePiX library.
  • tsptw.cc: A basic implementation of the TSPTW with the RL.
  • tsptw_ls.cc: A specialized implementation of the TSPTW with the RL.

Content:

Google or-tools
open source library

User's Manual

Google search

Search:

Welcome

Tutorial examples

Chapters

Part I: Basics
Part II: Customization
Part III: Routing
Part IV: Technicalities
Appendices