Description

With this algorithm, subtours in activity plans with given activity locations can be identified.

Subtour is defined like the following:

• A tour is a set of consecutive trips where the origin activity of the first trip and the destination activity of the last trip have the same location.
• This common location is called anchor point.
• A tour may consist of several subtours if another tour can be identified within it. Thus a subtour can be defined as a tour within another tour, while its trips not necessarily have to be consecutive.

Examples

1. Imagine an activity plan with the location sequence A-B-C-A. All trips belong to the same tour with the anchor point A.
2. Imagine the location sequence A-B-A-B-A. Two subtours exist with the anchor point A. The location sequence A-B-A-C-A has the same subtour structure.
3. Imagine the location sequence A-B-B-B-B-A. As tours/subtours may consist of a single trip, each trip between the locations B and B constitutes a subtour. Finally the first and the last trip of that location sequence is a subtour with anchor point A.

Usage in MATSim

Each subtour is assigned an index, starting with 0 for the first subtour identified. The algorithm returns a list with n elements, n being the number of trips in the given activity plan, which is the number of activities -1. The results for the above examples are:

1. 0-0-0
2. 0-0-1-1
3. 3-0-1-2-3

The algorithm is of a backtracking type which means that tour-like subtours are identifed first, and thus get the lower indices. This explains the indexation of the last example.

See more examples in the test class: org.matsim.population.algorithms.PlanAnalyzeSubtoursTest

The usage of the subtour indexation is as follows.

Plan plan = ...;
PlanAnalyzeSubtours past = new PlanAnalyzeSubtours();
testee.run(plan);
...
int numSubtours = past.getNumSubtours(); // get the number of subtours
int[] subtourIndexation = past.getSubtourIndexation(); // get the subtour indexation array