Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem

Typical problem and execution method

Transport route (delivery optimization) problem

A set of customers $ V = \ {0, 1, \ dots, n \} $ (where $ 0 $ represents the depot that is the starting point of the route) and a set of carriers $ M = \ {1, \ dots , m \} $ is given. Each carrier departs from the depot, delivers around the assigned customer set, and returns to the depot. For each customer $ i \ in V $, the service demand is $ a_i (\ ge 0) $, the maximum load capacity of each carrier $ k \ in M $ is $ u (\ ge 0) $, and the customer $ The transfer cost between i $ and customer $ j $ is $ c_ {ij} (\ ge 0) $. It is assumed that the demand of each customer is satisfied by one visit. Find routes for all vehicles to minimize travel costs.

--Also known as VRP (Vehicle Routing Problem). ――Delivery optimization is often called XX plan like delivery plan, but XX plan is old name.

Execution method

usage


Signature: vrp(g, nv, capa, demand='demand', cost='cost', method=None)
Docstring:
Transportation route problem
input
    g:Graph(node:demand, edge:cost)
    nv:Number of vehicles
    capa:Carrier capacity
    demand:Demand attribute character
    cost:Cost attribute character
    method:Method of calculation(ex. 'ortools')
output
List of apex pairs for each carrier

python


#CSV data
import pandas as pd, networkx as nx
from ortoolpy import vrp, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node1.csv')
tbe = pd.read_csv('data/edge1.csv')
g = graph_from_table(tbn, tbe)[0].to_directed()
networkx_draw(g)
nv, capa = 2, 3 #Number of vehicles, vehicle capacity
print(vrp(g, nv, capa))

result


[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

vrp.png

python


# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)
car num node1 node2 cost
0 0 0 0 3 10
1 0 1 0 2 10
2 0 2 3 5 1
3 0 3 5 2 1
4 1 0 0 4 10
5 1 1 0 1 10
6 1 2 4 1 1

python


#Sample data
import networkx as nx
from ortoolpy import vrp
nc, nv, capa = 5, 2, 3 #Number of customers, number of vehicles, vehicle capacity
g = nx.DiGraph()
g.add_node(0, demand=0)
g.add_nodes_from(range(1, nc + 1), demand=1)
g.add_edges_from([(0, i) for i in range(1, nc + 1)], cost=10)
g.add_edges_from([(i, 0) for i in range(1, nc + 1)], cost=10)
for i, j, t in ((1, 3, 16), (3, 5, 1), (5, 2, 1), (2, 4, 18), (4, 1, 1)):
    g.add_edge(i, j, cost=t)
    g.add_edge(j, i, cost=t)
print(vrp(g, nv, capa))

result


[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

How to use the Google OR-Tools solver

If " method ='ortools' "is added, the solver (approximate solution) of Google OR-Tools is used.

Caution

--Install Google OR-Tools with pip install or tools. --The cost should be an integer.

python


print(vrp(g, nv, capa, method='ortools'))

result


[[(0, 1), (1, 4), (4, 0)], [(0, 2), (2, 5), (5, 3), (3, 0)]]

data

Recommended Posts

Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Codeiq milk delivery route problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization --Typical problem-- Partition of a set problem
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Use combinatorial optimization
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Grouping by combinatorial optimization
Combinatorial optimization-minimum cut problem