Driver "End" array indexes are not same when we access them using router object.

[ManevN]

What version of OR-Tools and what language are you using? Version: 9.0.9048. Language: C#

**Which solver are you using: Routing Solver

**What operating system: Windows 10

Hey everyone,

I have following problem: My start and end arrays are initializes with this values: Start = { 0, 1} End = {4, 4}

When I'm trying to access for each vehicle using methods router.Start(vehicleId) and router.End(vehicleId), for vehicle with Id 0 methods returns correct values (0, 4), but for vehicle with id 1, we get (1, 5).

Anyone that can explain this or help to fix this bug ?

Why end index is increased, even there is no element 5, the last element is 4, which I use as depot(end point) for each vehicle.

[Mizux]

This is not a bug and it is intended. Thus as you correctly did, you must use routing.Start(vehicle_id)and routing.End(vehicle_id) to retrieve internal solver index. note: manager.IndexToNode(index) will work BUT not manager.NodeToIndex(4).

Long story: solver must have an unique index id for each vehicle start and end node. (because solver start to create empty route start->end for each vehicle).

In you case 0,1 are used "one" time so solver directly map both start vehicle to 0, 1 respectively. On the contrary 4 is used two time so solver has no choice but to create an extra node 5 and create the mapping

index -> node,
0 -> 0
1 -> 1
...
4 -> 4
5 -> 4

note: now, you should understand why routing.NodeToIndex(4) is not working because solver can't decide if it must return 4 or 5 i.e. to which vehicle's end node 4 is refering to, for consistency all NodeToIndex are forbidden for any start/end node (even if in your case it could be doable for start node)

EDIT: for implementation details: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing_index_manager.cc#L71-L75 and https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing_index_manager.cc#L77-L102

[ManevN]

Thanks, now I understand.

[Mizux]

Actually it's even worse, solver will always put vehicle end node at the end of its internal index range e.g. if ends are [1, 2, 3, 4] there will be move to the end and their node index will be reused.

Here a small samples to better understand relation between nodes and indices.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def main():
    """Entry point of the program."""
    location = 17
    starts = [5, 5, 7, 8]
    ends = [1, 2, 4, 4]
    vehicles = len(starts)
    assert len(starts) == len(ends)

    manager = pywrapcp.RoutingIndexManager(location, vehicles, starts, ends)
    routing = pywrapcp.RoutingModel(manager)

    print('Starts/Ends:')
    header = '| |'
    separator = '|---|'
    v_starts = '| start |'
    v_ends = '| end |'
    for v in range(manager.GetNumberOfVehicles()):
        header += f' vehicle {v} |'
        separator += '---|'
        v_starts += f' {starts[v]} |'
        v_ends += f' {ends[v]} |'
    print(header)
    print(separator)
    print(v_starts)
    print(v_ends)

    print('\nNodes:')
    print('| location | manager.GetNumberOfNodes | manager.GetNumberOfIndices | routing.nodes | routing.Size |')
    print('|---|---|---|---|---|')
    print(f'| {location} | {manager.GetNumberOfNodes()} | {manager.GetNumberOfIndices()} | {routing.nodes()} | {routing.Size()} |')

    print('Locations:')
    print('| node | index | routing.IsStart | routing.IsEnd |')
    print('|---|---|---|---|')
    for node in range(manager.GetNumberOfNodes()):
        if node in starts or node in ends:
            continue
        index = manager.NodeToIndex(node)
        print(f'| {node} | {index} | {routing.IsStart(index)} | {routing.IsEnd(index)} |')

    print('Start/End:')
    print('| vehicle | Start/end | node | index | routing.IsStart | routing.IsEnd |')
    print('|---|---|---|---|---|---|')
    for v in range(manager.GetNumberOfVehicles()):
        start_index = routing.Start(v)
        start_node = manager.IndexToNode(start_index)
        print(f'| {v} | start | {start_node} | {start_index} | {routing.IsStart(start_index)} | {routing.IsEnd(start_index)} |')
    for v in range(manager.GetNumberOfVehicles()):
        end_index = routing.End(v)
        end_node = manager.IndexToNode(end_index)
        print(f'| {v} | end  | {end_node} | {end_index} | {routing.IsStart(end_index)} | {routing.IsEnd(end_index)} |')

if __name__ == '__main__':
    main()

output:		vehicle 0	vehicle 1	vehicle 2	vehicle 3
start	5	5	7	8
end	1	2	4	4

Nodes:	location	manager.GetNumberOfNodes	manager.GetNumberOfIndices	routing.nodes	routing.Size
17	17	19	17	15

Locations:	node	index	routing.IsStart	routing.IsEnd
0	0	False	False
3	1	False	False
6	3	False	False
9	6	False	False
10	7	False	False
11	8	False	False
12	9	False	False
13	10	False	False
14	11	False	False
15	12	False	False
16	13	False	False

Start/End:	vehicle	Start/end	node	index	routing.IsStart	routing.IsEnd
0	start	5	2	True	False
1	start	5	14	True	False
2	start	7	4	True	False
3	start	8	5	True	False
0	end	1	15	False	True
1	end	2	16	False	True
2	end	4	17	False	True
3	end	4	18	False	True

Things to notice:

• Since we have two duplicates (node 5 and node 4) solver need need 2 extra indices to have an unique index for each vehicle start/stop and locations (i.e. 17 locations but 19 indices).

  • solver need to "create" an index for a vehicle 1 start since solver need an unique start index per vehicle.
  • solver need to "create" an index for a vehicle 3 end since solver need an unique end index per vehicle.

• all end node are moved to the last of the list aka [15, 16, 17, 18] (note: this is an internal optimization since end node don't have a next and need special treatment).

• routing.Size() return the number of node which are not end nodes (here 15 aka [0-14]) note: using the two properties above, we know that any index in range(routing.Size()) is not a vehicle end node...

• since end nodes are moved to the end, their respective "empty" node index are reused so all locations indices could be shifted e.g. node 9 is mapped to index 6

• same for start nodes which are moved to "empty" space e.g. start node 7 mapped to index 4

-> Allways use routing.Start(), routing.End(), manager.IndexToNode() or manager.NodeToIndex(). -> Location node is not necessarily equal to its index. -> to loop through ALL indices use manager.GetNumberOfIndices() (Python) or manager::num_indices() (C++)

EDIT: example is pushed to https://github.com/google/or-tools/blob/main/ortools/constraint_solver/samples/vrp_nodes_indices.py

[ManevN]

Thanks again Mizux, you comment are very helpful. I appreciate this.