blackopsrepl/vehicle-routing-python

1from solverforge_legacy.solver.test import ConstraintVerifier2 3from vehicle_routing.domain import Location, Vehicle, VehicleRoutePlan, Visit4from vehicle_routing.constraints import (5    define_constraints,6    vehicle_capacity,7    service_finished_after_max_end_time,8    minimize_travel_time,9)10 11from datetime import datetime, timedelta12 13# Driving times calculated using Haversine formula for realistic geographic distances.14# These test coordinates at 50 km/h average speed yield:15# LOCATION_1 to LOCATION_2: 40018 seconds (~11.1 hours, ~556 km)16# LOCATION_2 to LOCATION_3: 40025 seconds (~11.1 hours, ~556 km)17# LOCATION_1 to LOCATION_3: 11322 seconds (~3.1 hours, ~157 km)18 19LOCATION_1 = Location(latitude=0, longitude=0)20LOCATION_2 = Location(latitude=3, longitude=4)21LOCATION_3 = Location(latitude=-1, longitude=1)22 23DEPARTURE_TIME = datetime(2020, 1, 1)24MIN_START_TIME = DEPARTURE_TIME + timedelta(hours=2)25MAX_END_TIME = DEPARTURE_TIME + timedelta(hours=5)26SERVICE_DURATION = timedelta(hours=1)27 28constraint_verifier = ConstraintVerifier.build(29    define_constraints, VehicleRoutePlan, Vehicle, Visit30)31 32 33def test_vehicle_capacity_unpenalized():34    vehicleA = Vehicle(35        id="1", name="Alpha", capacity=100, home_location=LOCATION_1, departure_time=DEPARTURE_TIME36    )37    visit1 = Visit(38        id="2",39        name="John",40        location=LOCATION_2,41        demand=80,42        min_start_time=MIN_START_TIME,43        max_end_time=MAX_END_TIME,44        service_duration=SERVICE_DURATION,45    )46    connect(vehicleA, visit1)47 48    (49        constraint_verifier.verify_that(vehicle_capacity)50        .given(vehicleA, visit1)51        .penalizes_by(0)52    )53 54 55def test_vehicle_capacity_penalized():56    vehicleA = Vehicle(57        id="1", name="Alpha", capacity=100, home_location=LOCATION_1, departure_time=DEPARTURE_TIME58    )59    visit1 = Visit(60        id="2",61        name="John",62        location=LOCATION_2,63        demand=80,64        min_start_time=MIN_START_TIME,65        max_end_time=MAX_END_TIME,66        service_duration=SERVICE_DURATION,67    )68    visit2 = Visit(69        id="3",70        name="Paul",71        location=LOCATION_3,72        demand=40,73        min_start_time=MIN_START_TIME,74        max_end_time=MAX_END_TIME,75        service_duration=SERVICE_DURATION,76    )77 78    connect(vehicleA, visit1, visit2)79 80    (81        constraint_verifier.verify_that(vehicle_capacity)82        .given(vehicleA, visit1, visit2)83        .penalizes_by(20)84    )85 86 87def test_service_finished_after_max_end_time_unpenalized():88    vehicleA = Vehicle(89        id="1", name="Alpha", capacity=100, home_location=LOCATION_1, departure_time=DEPARTURE_TIME90    )91    visit1 = Visit(92        id="2",93        name="John",94        location=LOCATION_3,95        demand=80,96        min_start_time=MIN_START_TIME,97        max_end_time=MAX_END_TIME,98        service_duration=SERVICE_DURATION,99    )100 101    connect(vehicleA, visit1)102 103    (104        constraint_verifier.verify_that(service_finished_after_max_end_time)105        .given(vehicleA, visit1)106        .penalizes_by(0)107    )108 109 110def test_service_finished_after_max_end_time_penalized():111    vehicleA = Vehicle(112        id="1", name="Alpha", capacity=100, home_location=LOCATION_1, departure_time=DEPARTURE_TIME113    )114    visit1 = Visit(115        id="2",116        name="John",117        location=LOCATION_2,118        demand=80,119        min_start_time=MIN_START_TIME,120        max_end_time=MAX_END_TIME,121        service_duration=SERVICE_DURATION,122    )123 124    connect(vehicleA, visit1)125 126    # With Haversine formula:127    # Travel time to LOCATION_2: 40018 seconds = 11.12 hours128    # Arrival time: 2020-01-01 11:06:58129    # Service duration: 1 hour130    # End service: 2020-01-01 12:06:58131    # Max end time: 2020-01-01 05:00:00132    # Delay: 7 hours 6 minutes 58 seconds = 426.97 minutes, rounded up = 427 minutes133    (134        constraint_verifier.verify_that(service_finished_after_max_end_time)135        .given(vehicleA, visit1)136        .penalizes_by(427)137    )138 139 140def test_total_driving_time():141    vehicleA = Vehicle(142        id="1", name="Alpha", capacity=100, home_location=LOCATION_1, departure_time=DEPARTURE_TIME143    )144    visit1 = Visit(145        id="2",146        name="John",147        location=LOCATION_2,148        demand=80,149        min_start_time=MIN_START_TIME,150        max_end_time=MAX_END_TIME,151        service_duration=SERVICE_DURATION,152    )153    visit2 = Visit(154        id="3",155        name="Paul",156        location=LOCATION_3,157        demand=40,158        min_start_time=MIN_START_TIME,159        max_end_time=MAX_END_TIME,160        service_duration=SERVICE_DURATION,161    )162 163    connect(vehicleA, visit1, visit2)164 165    # With Haversine formula:166    # LOCATION_1 -> LOCATION_2: 40018 seconds167    # LOCATION_2 -> LOCATION_3: 40025 seconds168    # LOCATION_3 -> LOCATION_1: 11322 seconds169    # Total: 91365 seconds170    (171        constraint_verifier.verify_that(minimize_travel_time)172        .given(vehicleA, visit1, visit2)173        .penalizes_by(91365)174    )175 176 177def connect(vehicle: Vehicle, *visits: Visit):178    vehicle.visits = list(visits)179    for i in range(len(visits)):180        visit = visits[i]181        visit.vehicle = vehicle182        if i > 0:183            visit.previous_visit = visits[i - 1]184 185        if i < len(visits) - 1:186            visit.next_visit = visits[i + 1]187        visit.update_arrival_time()188