Hingga saat ini, kami telah membahas masalah pemilihan rute dengan batasan yang berlaku selama perjalanan kendaraan. Selanjutnya, kami menampilkan VRPTW yang juga memiliki batasan di depot: semua kendaraan perlu dimuat sebelum memisahkannya dan menghapus muatannya saat kembali. Karena hanya ada dua dok pemuatan yang tersedia, maksimal dua kendaraan dapat dimuat atau dibongkar secara bersamaan. Akibatnya, beberapa kendaraan harus menunggu kendaraan lain dimuat, menunda keberangkatan mereka dari depot. Masalahnya adalah menemukan rute kendaraan yang optimal untuk VRPTW yang juga memenuhi batasan bongkar muat di depot.
Contoh VRPTW dengan batasan resource
Diagram di bawah menunjukkan VRPTW dengan batasan resource.
Menyelesaikan contoh dengan OR-Tools
Bagian berikut menunjukkan cara mengatasi VRPTW dengan batasan resource menggunakan OR-Tools. Beberapa kode untuk contoh ini sama seperti dalam contoh VRPTW sebelumnya, jadi kami hanya akan menjelaskan bagian yang baru.
Membuat data
Kode berikut membuat data untuk contoh.
Python
def create_data_model(): """Stores the data for the problem.""" data = {} data["time_matrix"] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data["time_windows"] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (5, 14), # 3 (5, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 10), # 7 (5, 10), # 8 (0, 5), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 12), # 14 (10, 15), # 15 (5, 15), # 16 ] data["num_vehicles"] = 4 data["vehicle_load_time"] = 5 data["vehicle_unload_time"] = 5 data["depot_capacity"] = 2 data["depot"] = 0 return data
C++
struct DataModel { const std::vector<std::vector<int64_t>> time_matrix{ {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7}, {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14}, {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9}, {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16}, {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14}, {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8}, {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5}, {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10}, {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6}, {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5}, {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4}, {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10}, {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8}, {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6}, {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2}, {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9}, {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0}, }; const std::vector<std::pair<int64_t, int64_t>> time_windows{ {0, 5}, // depot {7, 12}, // 1 {10, 15}, // 2 {5, 14}, // 3 {5, 13}, // 4 {0, 5}, // 5 {5, 10}, // 6 {0, 10}, // 7 {5, 10}, // 8 {0, 5}, // 9 {10, 16}, // 10 {10, 15}, // 11 {0, 5}, // 12 {5, 10}, // 13 {7, 12}, // 14 {10, 15}, // 15 {5, 15}, // 16 }; const int num_vehicles = 4; const int vehicle_load_time = 5; const int vehicle_unload_time = 5; const int depot_capacity = 2; const RoutingIndexManager::NodeIndex depot{0}; };
Java
static class DataModel { public final long[][] timeMatrix = { {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7}, {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14}, {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9}, {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16}, {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14}, {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8}, {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5}, {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10}, {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6}, {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5}, {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4}, {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10}, {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8}, {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6}, {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2}, {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9}, {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0}, }; public final long[][] timeWindows = { {0, 5}, // depot {7, 12}, // 1 {10, 15}, // 2 {5, 14}, // 3 {5, 13}, // 4 {0, 5}, // 5 {5, 10}, // 6 {0, 10}, // 7 {5, 10}, // 8 {0, 5}, // 9 {10, 16}, // 10 {10, 15}, // 11 {0, 5}, // 12 {5, 10}, // 13 {7, 12}, // 14 {10, 15}, // 15 {5, 15}, // 16 }; public final int vehicleNumber = 4; public final int vehicleLoadTime = 5; public final int vehicleUnloadTime = 5; public final int depotCapacity = 2; public final int depot = 0; }
C#
class DataModel { public long[,] TimeMatrix = { { 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 }, { 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 }, { 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 }, { 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 }, { 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 }, { 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 }, { 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 }, { 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 }, { 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 }, { 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 }, { 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 }, { 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 }, { 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 }, { 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 }, { 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 }, { 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 }, { 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 }, }; public long[,] TimeWindows = { { 0, 5 }, // depot { 7, 12 }, // 1 { 10, 15 }, // 2 { 5, 14 }, // 3 { 5, 13 }, // 4 { 0, 5 }, // 5 { 5, 10 }, // 6 { 0, 10 }, // 7 { 5, 10 }, // 8 { 0, 5 }, // 9 { 10, 16 }, // 10 { 10, 15 }, // 11 { 0, 5 }, // 12 { 5, 10 }, // 13 { 7, 12 }, // 14 { 10, 15 }, // 15 { 5, 15 }, // 16 }; public int VehicleNumber = 4; public int VehicleLoadTime = 5; public int VehicleUnloadTime = 5; public int DepotCapacity = 2; public int Depot = 0; };
Data tersebut mencakup hal berikut:
time_matrix
: Array waktu perjalanan antarlokasi.time_windows
: Array periode waktu untuk kunjungan yang diminta ke lokasi.vehicle_load_time
: Waktu yang diperlukan untuk memuat kendaraan.vehicle_unload_time
: Waktu yang diperlukan untuk membongkar kendaraan.depot_capacity
: Jumlah maksimum kendaraan yang dapat memuat atau membongkar muatan secara bersamaan.
Menambahkan jangka waktu untuk pemuatan dan penurunan muatan
Kode berikut menambahkan jangka waktu untuk memuat dan membongkar kendaraan di depot.
Jendela ini, yang dibuat dengan metode FixedDurationIntervalVar
, adalah
periode waktu variabel, yang berarti jendela tersebut tidak memiliki waktu mulai dan waktu berakhir yang tetap
(tidak seperti periode waktu di lokasi). Lebar jendela ditentukan
oleh vehicle_load_time
dan vehicle_unload_time
, yang kebetulan
sama dalam contoh ini.
Python
solver = routing.solver() intervals = [] for i in range(data["num_vehicles"]): # Add time windows at start of routes intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data["vehicle_load_time"], "depot_interval", ) ) # Add time windows at end of routes. intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data["vehicle_unload_time"], "depot_interval", ) )
C++
Solver* solver = routing.solver(); std::vector<IntervalVar*> intervals; for (int i = 0; i < data.num_vehicles; ++i) { // Add load duration at start of routes intervals.push_back(solver->MakeFixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data.vehicle_load_time, "depot_interval")); // Add unload duration at end of routes. intervals.push_back(solver->MakeFixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data.vehicle_unload_time, "depot_interval")); }
Java
Solver solver = routing.solver(); IntervalVar[] intervals = new IntervalVar[data.vehicleNumber * 2]; for (int i = 0; i < data.vehicleNumber; ++i) { // Add load duration at start of routes intervals[2 * i] = solver.makeFixedDurationIntervalVar( timeDimension.cumulVar(routing.start(i)), data.vehicleLoadTime, "depot_interval"); // Add unload duration at end of routes. intervals[2 * i + 1] = solver.makeFixedDurationIntervalVar( timeDimension.cumulVar(routing.end(i)), data.vehicleUnloadTime, "depot_interval"); }
C#
Solver solver = routing.solver(); IntervalVar[] intervals = new IntervalVar[data.VehicleNumber * 2]; for (int i = 0; i < data.VehicleNumber; ++i) { // Add load duration at start of routes intervals[2 * i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.Start(i)), data.VehicleLoadTime, "depot_interval"); // Add unload duration at end of routes. intervals[2 * i + 1] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.End(i)), data.VehicleUnloadTime, "depot_interval"); }
Menambahkan batasan resource di depot
Kode berikut membuat batasan bahwa maksimal dua kendaraan dapat dimuat atau dibongkar secara bersamaan.
Python
depot_usage = [1 for _ in range(len(intervals))] solver.Add( solver.Cumulative(intervals, depot_usage, data["depot_capacity"], "depot") )
C++
std::vector<int64_t> depot_usage(intervals.size(), 1); solver->AddConstraint(solver->MakeCumulative(intervals, depot_usage, data.depot_capacity, "depot"));
Java
long[] depotUsage = new long[intervals.length]; Arrays.fill(depotUsage, 1); solver.addConstraint(solver.makeCumulative(intervals, depotUsage, data.depotCapacity, "depot"));
C#
long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray(); solver.Add(solver.MakeCumulative(intervals, depot_usage, data.DepotCapacity, "depot"));
depot_capacity
adalah jumlah maksimum kendaraan yang dapat dimuat atau
dibongkar secara bersamaan, yaitu 2 dalam contoh ini.
depot_usage
adalah vektor yang berisi jumlah relatif ruang yang diperlukan oleh
setiap kendaraan selama pemuatan (atau penghapusan muatan). Dalam contoh ini, kami berasumsi bahwa semua
kendaraan memerlukan jumlah ruang yang sama, sehingga depot_usage
berisi semua kendaraan.
Ini berarti jumlah maksimum kendaraan yang dapat dimuat secara bersamaan adalah 2.
Menjalankan program
Berikut ini adalah output program.
Route for vehicle 0: 0 Time(5,5) -> 8 Time(8,8) -> 14 Time(11,11) -> 16 Time(13,13) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 1: 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 2: 0 Time(5,5) -> 7 Time(7,7) -> 1 Time(11,11) -> 4 Time(13,13) -> 3 Time(14,14) -> 0 Time(25,25) Time of the route: 25min Route for vehicle 3: 0 Time(0,0) -> 9 Time(2,3) -> 5 Time(4,5) -> 6 Time(6,9) -> 2 Time(10,12) -> 10 Time(14,16) -> 0 Time(25,25) Time of the route: 25min Total time of all routes: 90min
Lihat contoh VRPTW sebelumnya untuk penjelasan tentang output.
Perhatikan bahwa kendaraan 1 dan 3 meninggalkan depot pada waktu 0. Kendaraan 0 dan 2, yang
harus menunggu yang lain dimuat, berangkat pada waktu 5, dengan nilai
vehicle_load_time
.
Diagram di bawah menunjukkan solusinya.
Selesaikan program
Program lengkap untuk masalah pemilihan rute kendaraan dengan kapasitas dengan batasan resource ditampilkan di bawah ini.
Python
"""Vehicles Routing Problem (VRP) with Resource Constraints.""" from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data["time_matrix"] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data["time_windows"] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (5, 14), # 3 (5, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 10), # 7 (5, 10), # 8 (0, 5), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 12), # 14 (10, 15), # 15 (5, 15), # 16 ] data["num_vehicles"] = 4 data["vehicle_load_time"] = 5 data["vehicle_unload_time"] = 5 data["depot_capacity"] = 2 data["depot"] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") time_dimension = routing.GetDimensionOrDie("Time") total_time = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) plan_output += ( f"{manager.IndexToNode(index)}" f" Time({solution.Min(time_var)}, {solution.Max(time_var)})" " -> " ) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += ( f"{manager.IndexToNode(index)}" f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n" ) plan_output += f"Time of the route: {solution.Min(time_var)}min\n" print(plan_output) total_time += solution.Min(time_var) print(f"Total time of all routes: {total_time}min") def main(): """Solve the VRP with time windows.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager( len(data["time_matrix"]), data["num_vehicles"], data["depot"] ) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def time_callback(from_index, to_index): """Returns the travel time between the two nodes.""" # Convert from routing variable Index to time matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data["time_matrix"][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(time_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Time Windows constraint. time = "Time" routing.AddDimension( transit_callback_index, 60, # allow waiting time 60, # maximum time per vehicle False, # Don't force start cumul to zero. time, ) time_dimension = routing.GetDimensionOrDie(time) # Add time window constraints for each location except depot. for location_idx, time_window in enumerate(data["time_windows"]): if location_idx == 0: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # Add time window constraints for each vehicle start node. for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange( data["time_windows"][0][0], data["time_windows"][0][1] ) # Add resource constraints at the depot. solver = routing.solver() intervals = [] for i in range(data["num_vehicles"]): # Add time windows at start of routes intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data["vehicle_load_time"], "depot_interval", ) ) # Add time windows at end of routes. intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data["vehicle_unload_time"], "depot_interval", ) ) depot_usage = [1 for _ in range(len(intervals))] solver.Add( solver.Cumulative(intervals, depot_usage, data["depot_capacity"], "depot") ) # Instantiate route start and end times to produce feasible times. for i in range(data["num_vehicles"]): routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i)) ) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i))) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) else: print("No solution found !") if __name__ == "__main__": main()
C++
#include <cstdint> #include <sstream> #include <string> #include <utility> #include <vector> #include "ortools/constraint_solver/routing.h" #include "ortools/constraint_solver/routing_enums.pb.h" #include "ortools/constraint_solver/routing_index_manager.h" #include "ortools/constraint_solver/routing_parameters.h" namespace operations_research { struct DataModel { const std::vector<std::vector<int64_t>> time_matrix{ {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7}, {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14}, {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9}, {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16}, {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14}, {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8}, {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5}, {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10}, {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6}, {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5}, {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4}, {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10}, {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8}, {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6}, {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2}, {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9}, {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0}, }; const std::vector<std::pair<int64_t, int64_t>> time_windows{ {0, 5}, // depot {7, 12}, // 1 {10, 15}, // 2 {5, 14}, // 3 {5, 13}, // 4 {0, 5}, // 5 {5, 10}, // 6 {0, 10}, // 7 {5, 10}, // 8 {0, 5}, // 9 {10, 16}, // 10 {10, 15}, // 11 {0, 5}, // 12 {5, 10}, // 13 {7, 12}, // 14 {10, 15}, // 15 {5, 15}, // 16 }; const int num_vehicles = 4; const int vehicle_load_time = 5; const int vehicle_unload_time = 5; const int depot_capacity = 2; const RoutingIndexManager::NodeIndex depot{0}; }; //! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time"); int64_t total_time{0}; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for vehicle " << vehicle_id << ":"; std::ostringstream route; while (!routing.IsEnd(index)) { auto time_var = time_dimension.CumulVar(index); route << manager.IndexToNode(index).value() << " Time(" << solution.Min(time_var) << ", " << solution.Max(time_var) << ") -> "; index = solution.Value(routing.NextVar(index)); } auto time_var = time_dimension.CumulVar(index); LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time(" << solution.Min(time_var) << ", " << solution.Max(time_var) << ")"; LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min"; total_time += solution.Min(time_var); } LOG(INFO) << "Total time of all routes: " << total_time << "min"; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; } void VrpTimeWindows() { // Instantiate the data problem. DataModel data; // Create Routing Index Manager RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles, data.depot); // Create Routing Model. RoutingModel routing(manager); // Create and register a transit callback. const int transit_callback_index = routing.RegisterTransitCallback( [&data, &manager](const int64_t from_index, const int64_t to_index) -> int64_t { // Convert from routing variable Index to time matrix NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); const int to_node = manager.IndexToNode(to_index).value(); return data.time_matrix[from_node][to_node]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index); // Add Time constraint. const std::string time = "Time"; routing.AddDimension(transit_callback_index, // transit callback index int64_t{30}, // allow waiting time int64_t{30}, // maximum time per vehicle false, // Don't force start cumul to zero time); const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time); // Add time window constraints for each location except depot. for (int i = 1; i < data.time_windows.size(); ++i) { const int64_t index = manager.NodeToIndex(RoutingIndexManager::NodeIndex(i)); time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first, data.time_windows[i].second); } // Add time window constraints for each vehicle start node. for (int i = 0; i < data.num_vehicles; ++i) { const int64_t index = routing.Start(i); time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first, data.time_windows[0].second); } // Add resource constraints at the depot. Solver* solver = routing.solver(); std::vector<IntervalVar*> intervals; for (int i = 0; i < data.num_vehicles; ++i) { // Add load duration at start of routes intervals.push_back(solver->MakeFixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data.vehicle_load_time, "depot_interval")); // Add unload duration at end of routes. intervals.push_back(solver->MakeFixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data.vehicle_unload_time, "depot_interval")); } std::vector<int64_t> depot_usage(intervals.size(), 1); solver->AddConstraint(solver->MakeCumulative(intervals, depot_usage, data.depot_capacity, "depot")); // Instantiate route start and end times to produce feasible times. for (int i = 0; i < data.num_vehicles; ++i) { routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i))); routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.End(i))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.set_first_solution_strategy( FirstSolutionStrategy::PATH_CHEAPEST_ARC); // Solve the problem. const Assignment* solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpTimeWindows(); return EXIT_SUCCESS; }
Java
package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.Assignment; import com.google.ortools.constraintsolver.FirstSolutionStrategy; import com.google.ortools.constraintsolver.IntVar; import com.google.ortools.constraintsolver.IntervalVar; import com.google.ortools.constraintsolver.RoutingDimension; import com.google.ortools.constraintsolver.RoutingIndexManager; import com.google.ortools.constraintsolver.RoutingModel; import com.google.ortools.constraintsolver.RoutingSearchParameters; import com.google.ortools.constraintsolver.Solver; import com.google.ortools.constraintsolver.main; import java.util.Arrays; import java.util.logging.Logger; /** Minimal VRP with Resource Constraints.*/ public class VrpResources { private static final Logger logger = Logger.getLogger(VrpResources.class.getName()); static class DataModel { public final long[][] timeMatrix = { {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7}, {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14}, {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9}, {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16}, {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14}, {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8}, {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5}, {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10}, {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6}, {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5}, {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4}, {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10}, {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8}, {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6}, {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2}, {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9}, {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0}, }; public final long[][] timeWindows = { {0, 5}, // depot {7, 12}, // 1 {10, 15}, // 2 {5, 14}, // 3 {5, 13}, // 4 {0, 5}, // 5 {5, 10}, // 6 {0, 10}, // 7 {5, 10}, // 8 {0, 5}, // 9 {10, 16}, // 10 {10, 15}, // 11 {0, 5}, // 12 {5, 10}, // 13 {7, 12}, // 14 {10, 15}, // 15 {5, 15}, // 16 }; public final int vehicleNumber = 4; public final int vehicleLoadTime = 5; public final int vehicleUnloadTime = 5; public final int depotCapacity = 2; public final int depot = 0; } /// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective : " + solution.objectiveValue()); // Inspect solution. RoutingDimension timeDimension = routing.getMutableDimension("Time"); long totalTime = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); String route = ""; while (!routing.isEnd(index)) { IntVar timeVar = timeDimension.cumulVar(index); route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + "," + solution.max(timeVar) + ") -> "; index = solution.value(routing.nextVar(index)); } IntVar timeVar = timeDimension.cumulVar(index); route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + "," + solution.max(timeVar) + ")"; logger.info(route); logger.info("Time of the route: " + solution.min(timeVar) + "min"); totalTime += solution.min(timeVar); } logger.info("Total time of all routes: " + totalTime + "min"); } public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate the data problem. final DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.timeMatrix.length, data.vehicleNumber, data.depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return data.timeMatrix[fromNode][toNode]; }); // Define cost of each arc. routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Time constraint. routing.addDimension(transitCallbackIndex, // transit callback 30, // allow waiting time 30, // vehicle maximum capacities false, // start cumul to zero "Time"); RoutingDimension timeDimension = routing.getMutableDimension("Time"); // Add time window constraints for each location except depot. for (int i = 1; i < data.timeWindows.length; ++i) { long index = manager.nodeToIndex(i); timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]); } // Add time window constraints for each vehicle start node. for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]); } // Add resource constraints at the depot. Solver solver = routing.solver(); IntervalVar[] intervals = new IntervalVar[data.vehicleNumber * 2]; for (int i = 0; i < data.vehicleNumber; ++i) { // Add load duration at start of routes intervals[2 * i] = solver.makeFixedDurationIntervalVar( timeDimension.cumulVar(routing.start(i)), data.vehicleLoadTime, "depot_interval"); // Add unload duration at end of routes. intervals[2 * i + 1] = solver.makeFixedDurationIntervalVar( timeDimension.cumulVar(routing.end(i)), data.vehicleUnloadTime, "depot_interval"); } long[] depotUsage = new long[intervals.length]; Arrays.fill(depotUsage, 1); solver.addConstraint(solver.makeCumulative(intervals, depotUsage, data.depotCapacity, "depot")); // Instantiate route start and end times to produce feasible times. for (int i = 0; i < data.vehicleNumber; ++i) { routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i))); routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC) .build(); // Solve the problem. Assignment solution = routing.solveWithParameters(searchParameters); // Print solution on console. printSolution(data, routing, manager, solution); } }
C#
using System; using System.Linq; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; /// <summary> /// Vehicles Routing Problem (VRP) with Resource Constraints. /// </summary> public class VrpResources { class DataModel { public long[,] TimeMatrix = { { 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 }, { 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 }, { 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 }, { 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 }, { 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 }, { 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 }, { 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 }, { 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 }, { 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 }, { 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 }, { 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 }, { 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 }, { 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 }, { 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 }, { 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 }, { 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 }, { 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 }, }; public long[,] TimeWindows = { { 0, 5 }, // depot { 7, 12 }, // 1 { 10, 15 }, // 2 { 5, 14 }, // 3 { 5, 13 }, // 4 { 0, 5 }, // 5 { 5, 10 }, // 6 { 0, 10 }, // 7 { 5, 10 }, // 8 { 0, 5 }, // 9 { 10, 16 }, // 10 { 10, 15 }, // 11 { 0, 5 }, // 12 { 5, 10 }, // 13 { 7, 12 }, // 14 { 10, 15 }, // 15 { 5, 15 }, // 16 }; public int VehicleNumber = 4; public int VehicleLoadTime = 5; public int VehicleUnloadTime = 5; public int DepotCapacity = 2; public int Depot = 0; }; /// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. RoutingDimension timeDimension = routing.GetMutableDimension("Time"); long totalTime = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); var index = routing.Start(i); while (routing.IsEnd(index) == false) { var timeVar = timeDimension.CumulVar(index); Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar), solution.Max(timeVar)); index = solution.Value(routing.NextVar(index)); } var endTimeVar = timeDimension.CumulVar(index); Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar), solution.Max(endTimeVar)); Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar)); totalTime += solution.Min(endTimeVar); } Console.WriteLine("Total time of all routes: {0}min", totalTime); } public static void Main(String[] args) { // Instantiate the data problem. DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.TimeMatrix.GetLength(0), data.VehicleNumber, data.Depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => { // Convert from routing variable Index to // distance matrix NodeIndex. var fromNode = manager.IndexToNode(fromIndex); var toNode = manager.IndexToNode(toIndex); return data.TimeMatrix[fromNode, toNode]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Distance constraint. routing.AddDimension(transitCallbackIndex, // transit callback 30, // allow waiting time 30, // vehicle maximum capacities false, // start cumul to zero "Time"); RoutingDimension timeDimension = routing.GetMutableDimension("Time"); // Add time window constraints for each location except depot. for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) { long index = manager.NodeToIndex(i); timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]); } // Add time window constraints for each vehicle start node. for (int i = 0; i < data.VehicleNumber; ++i) { long index = routing.Start(i); timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]); } // Add resource constraints at the depot. Solver solver = routing.solver(); IntervalVar[] intervals = new IntervalVar[data.VehicleNumber * 2]; for (int i = 0; i < data.VehicleNumber; ++i) { // Add load duration at start of routes intervals[2 * i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.Start(i)), data.VehicleLoadTime, "depot_interval"); // Add unload duration at end of routes. intervals[2 * i + 1] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.End(i)), data.VehicleUnloadTime, "depot_interval"); } long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray(); solver.Add(solver.MakeCumulative(intervals, depot_usage, data.DepotCapacity, "depot")); // Instantiate route start and end times to produce feasible times. for (int i = 0; i < data.VehicleNumber; ++i) { routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i))); routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }