Function test_small_example_from_cattaruzza_paper

tests/test_Route.py:706–774

Tests a small multi-trip VRP example. The data are from [1]_, corresponding to their Figure 1. References ---------- .. [1] D. Cattaruzza, N. Absi, and D. Feillet (2016). The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates. *Transpor

()

def test_small_example_from_cattaruzza_paper():
    """
    Tests a small multi-trip VRP example. The data are from [1]_, corresponding
    to their Figure 1.

    References
    ----------
    .. [1] D. Cattaruzza, N. Absi, and D. Feillet (2016). The Multi-Trip
           Vehicle Routing Problem with Time Windows and Release Dates.
           *Transportation Science* 50(2): 676-693.
           https://doi.org/10.1287/trsc.2015.0608.
    """
    depot = Depot(0, 0, tw_early=0, tw_late=200, service_duration=20)
    clients = [
        # Figure 1 details release times for some clients. But release times
        # are not actually binding in the example, so they are not needed.
        Client(0, 0, tw_early=100, tw_late=120, service_duration=5),
        Client(0, 0, tw_early=50, tw_late=75, service_duration=5),
        Client(0, 0, tw_early=50, tw_late=75, service_duration=5),
        Client(0, 0, tw_early=50, tw_late=100, service_duration=5),
        Client(0, 0, tw_early=50, tw_late=100, service_duration=5),
    ]

    matrix = [
        [0, 5, 15, 20, 10, 15],
        [5, 0, 20, 20, 15, 15],
        [15, 20, 0, 40, 20, 30],
        [20, 20, 40, 0, 30, 10],
        [10, 15, 20, 30, 0, 20],
        [15, 15, 30, 10, 20, 0],
    ]

    data = ProblemData(
        clients=clients,
        depots=[depot],
        vehicle_types=[VehicleType(reload_depots=[0])],
        distance_matrices=[matrix],
        duration_matrices=[matrix],
    )

    trip1 = Trip(data, [5, 3], 0)
    trip2 = Trip(data, [1], 0)
    trip3 = Trip(data, [4], 0)
    trip4 = Trip(data, [2], 0)
    route = Route(data, [trip1, trip2, trip3, trip4], 0)

    # These values were verified from the paper, and where needed calculated
    # manually. Note that the paper setting requires the first trip to start
    # immediately, which results in 15 wait duration. We do not require this,
    # instead starting a little later to avoid the wait duration. The other
    # quantities reported below match the paper.
    assert_equal(route.start_time(), 15)
    assert_equal(route.end_time(), 95)
    assert_equal(route.time_warp(), 75 + 55)  # two time warp violations
    assert_equal(route.slack(), 0)  # there is time warp, so no slack
    assert_equal(route.service_duration(), 25 + 80)  # at clients and depots
    assert_equal(route.travel_duration(), 105)