The official manual gives sample code for using OR-Tools to solve problems:

https://developers.google.com/optimization/routing/vrp

The python code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
"""Simple Vehicles Routing Problem (VRP).

This is a sample using the routing library python wrapper to solve a VRP
problem.
A description of the problem can be found here:
http://en.wikipedia.org/wiki/Vehicle_routing_problem.

Distances are in meters.
"""

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["distance_matrix"] = [
# fmt: off
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
# fmt: on
]
data["num_vehicles"] = 4
data["depot"] = 0
return data


def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route distances: {max_route_distance}m")


def main():
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model()

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["distance_matrix"][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)

# Output log
search_parameters.log_search = True

# 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()

The output of this code is as follows:

Read more »

UUID is usually used to generate unique identifiers, such as the ID field of the database, user account number, etc.

The following are some commonly used functions, for more information: https://docs.python.org/3/library/uuid.html.

uuid.uuid1(node=None, clock_seq=None)

Generate a UUID from a host ID, sequence number, and the current time. If node is not given, getnode() is used to obtain the hardware address. If clock_seq is given, it is used as the sequence number; otherwise a random 14-bit sequence number is chosen.

uuid.uuid3(namespace, name)

Read more »

Step 1: Find the hosts file from the following location: C:\windows\system32\drivers\etc, as shown in the figure below:

Step 2: Add records according to the format of "ip domain name", and the IP and domain name need to be separated by spaces, as shown below:

Note: You can open the hosts file as .txt file and modify it.

Read more »

The TSP problem usually requires finding a path with the minimum weight (or cost) that starts from the starting point, passes through all other nodes in sequence without repetition, and finally returns to the starting point


Parameter Description

Parameter Description
VV The collection of all nodes
nn Number of nodes
i,ji,j Node Number, i,jVi,j \in V
cijc_{ij} The weight (or cost) of edge (i,j)(i,j)
xijx_{ij} 0-1 decision variable, where 1 means visiting edge (i, j) and 0 means not visiting edge (i, j)

Read more »

I have recently read some literature on truck scheduling in mining areas which is generally a combinatorial optimization problem. The following is a brief summary of a common scheduling model in the literature.


Parameter Description

Parameter Description Unit
ii Loading area number, i=1,,mi=1,⋯,m
jj Unloading area number, j=1,,nj=1,⋯,n
rr Truck number, r=1,,Kr=1,⋯,K
GG Total Target Mineral Production tt
TT Length of each work shift hh
KK Maximum number of trucks available
CC Rated load capacity of each truck tt
tlt_l Average loading time of each truck hh
tut_u Average uninstall time of each truck hh
vfv_f Average speed of a fully loaded truck km/hkm/h
vev_e Average speed of an empty truck km/hkm/h
cfc_f The transportation cost per unit distance when the truck is fully loaded RMB/kmRMB/km
cec_e The transportation cost per unit distance when the truck is empty RMB/kmRMB/km
dijd_{ij} The shortest path distance from loading area ii to unloading area jj kmkm
fjf_j Requirements of unloading area jj tt
gig_i Total amount of minerals in loading area ii tt
hjh_j The maximum unloading amount of unloading area jj tt
BcB_c The maximum number of loading times at all loading points within one shift
aia_i Mineral grade in loading area ii %
ee Desired mineral grade %
α\alpha Maximum allowed grade error %
xrijx_{rij} The number of full trips of truck rr from the loading area ii to the unloading area jj
yrjiy_{rji} The number of empty trips of truck rr from the unloading area jj to the loading area ii

Read more »

Deep Q-Network (DQN) is a deep reinforcement learning method, first proposed by Google DeepMind team in 2013 [Paper]. This algorithm introduces a neural network to replace the cumulative expected return storage form in the Q-learning algorithm, and can effectively solve problems with high-dimensional state spaces. The DeepMind team creatively combines convolutional neural networks in deep learning and Q-learning in reinforcement learning to train agents to learn how to control characters in Atari games to achieve good game performance.


Neural Network

The DQN algorithm takes the state of the agent as the input of the neural network, and then uses the neural network to calculate the Q values corresponding to all actions.

Online Network and Target Network

Read more »

This project is also part of my master's thesis, and it includes two aspects: global path planning of each robot and collaborative planning of multiple robots. My master's thesis (Written in Chinese) can be downloaded here.

Global Path Planning for Each Robot

Abstract:

To solve the routing problem in Mobile Robot Fulfillment System, firstly, a method based on traditional A* algorithm is proposed, and then a method based on improved A* algorithm considering task priority and utilization frequency of path nodes is further designed. Finally, a Markov decision process describing the problem is established, and a method based on Q-learning is proposed. Results of computational experiments show that these algorithms can quickly solve the problem. The methods based on the traditional A* algorithm and Q-learning can both obtain the shortest paths, and the method based on improved A* algorithm can effectively balance the traffic flow and significantly reduce the number of potential collisions.

Comparison between Traditional A* Algorithm and Improved A* Algorithm

Read more »

More details about this project can be found in this paper. Here is a brief introduction to the project. This project is part of my master's thesis. My master's thesis (Written in Chinese) can be downloaded here.

Abstract:
This paper studies a task scheduling problem in the context of the mobile robot fulfillment system (MRFS), a parts-to-picker storage system where mobile robots bring movable racks to workstations. It determines the assignment of tasks of transporting racks to a fleet of robots with the objective of makespan minimization. A mixed integer programming model is presented to describe the problem. Aimed at quickly finding good solutions to this NP-hard problem, two heuristic rules and an ant colony optimization algorithm are developed. Computational experiments are conducted to evaluate the performance of the proposed heuristic solution procedures. It shows that the ant colony optimization algorithm generally has the best performance.


Mathematical Models

A mixed integer programming model is presented to describe the problem as follows:

Read more »
0%