VRP问题及Google工具or-tools的基础调研。

TSP问题与VRP问题

TSP问题

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。
问题定义如下：给定若干城市与城市间的距离集合，求经过所有城市恰好一次的最短回路。即：给定图G=(V, E, W)，其中V为顶点集合，|V|=n，E为边集合，W为边权函数，求集合{1, 2, …, n}的一个排列$\pi$ 使得下式最小。
$$
\sum_{i=1}^{n-1}w(v_{\pi(i) },v_{\pi(i+1)})+w(v_{\pi(n)},v_{\pi(1)})
$$

问题同样可以用整数线性规划问题来形式化，我们用数字1,…,n标记这些城市，并定义：
$$
x_{ij}= \begin{cases}1, & \text {路径选择从i到j} \\ 0, & \text{otherwise} \end{cases}
$$

对于i=1,2,…,n,令$c_{ij}$ 表示从城市i到j的距离，$u_{i}$为一个正整数变量，那么TSP问题可以写成下面的整数线性规划问题:
$$
\min \sum_{i=0}^n\sum_{j\neq i,j=1}^n x_{ij}w_{ij} \\
x_{ij}\in \{0,1\} \ \ \ \ \ \ \ \ \ \ i,j=1,…,n \\
u_i \in {Z} \ \ \ \ \ \ \ \ \ \ i=1,…,n \\
\sum_{i=1,i\neq j}^n x_{ij}=1 \ \ \ \ \ j=1,…,n \\
\sum_{j=1,j\neq i}^n x_{ij}=1 \ \ \ \ \ i=1,…,n \\
u_i-u_j+nx_{ij}\leq n-1 \ \ \ \ 2\leq i\neq j \leq n
$$
第一组等式要求每个城市都能另一个城市前来，而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条，而不是两条或者多条分散的路径在一起覆盖的。

证明可行解中的每个子回路经过1号城市（注意到等式保证了只有一条这样的路径），就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有$x_{ij}=1$ 对应的不等式求和的话，对 k 步不经过1号城市的任何子回路，我们得到：$nk\leq (n-1)k$, 矛盾。

VRP问题

一般VRP问题

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。

设有一场站，共有M 辆货车，车辆容量为Q，有N位顾客，每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。

类似的，问题同样可以用整数线性规划问题来形式化，我们用数字0,…,n-1标记这些城市，记其全集为V，并定义：
$$
x_{ij}= \begin{cases}1, & \text {路径选择从i到j} \\ 0, & \text{otherwise} \end{cases}
$$
对于i=0,1,…,n-1,$c_{ij}$ 表示从城市i到j的距离，0为初始点，那么VRP问题可以写成下面的整数线性规划问题:

$$
\min \sum_{i\in V}\sum_{j\in V} x_{ij}w_{ij} \\
x_{ij} \in \{0, 1\} \ \ \ \ \ \ \ \ \ \ \ i,j \in V \\
\sum_{i\in V}^n x_{ij}=1 \ \ \ \ \ j \in V, j \neq 0 \\
\sum_{j\in V}^n x_{ij}=1 \ \ \ \ \ i \in V,i \neq 0 \\
\sum_{i\in V}^n x_{i0}=K \\
\sum_{j\in V}^n x_{0j}=K \\
\sum_{i\notin S}\sum_{j\in S}x_{ij} \geq r(S) \ \ \ \ \ \forall S \subset V \verb||{0}, S \neq \emptyset
$$
其中r(s)是服务集合S中各节点所需的最少车辆数目。

变种VRP问题

与一般的VR问题相比，变种的VRP问题通常增加了一些额外的限制，这些限制通常包括:装卸货的顺序，时间（时间窗），是否要求回到场点，容量限制等。以下是几种比较常见的变种VRP问题：

有时间窗车辆路径问题（VRPTW，VRP with Time Windows）
考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。
在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。
接送货物的车辆路径问题（VRPPD，Vehicle Routing Problem with Pickup and Delivery）
货物需要从一个地点转移到另一个地点。VRPPD的目标是找到一组最好的路径，十多分钟若干车辆可以成本最低地运送货物。
按序接送货物的车辆路径问题（Vehicle Routing Problem with LIFO）
与VRPPD类似，问题需要把若干货物从一个地点转移到另外的地点，但不同的是，限制了装卸货物的顺序。为了避免临时卸货再装货，问题要求最近接收的货物需要最早的被运送、卸货。
开放的车辆路径问题（OVRP，Open Vehicle Routing Problem）
车辆在运送货物后并不需要返回场点。

or-tools 工具包介绍

or-tools 功能介绍

or-tools 是 Google 的优化搜索工具。

Google 优化工具包括：

约束编程解决方案(N-皇后问题，数字谜问题)

Constraint programming is the name given to identifying feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints.
为线性规划和混合整数规划解决方案提供简单统一的接口，包括 CBC, CLP, GLOP, GLPK, Gurobi, SCIP, 和 Sulum。
背包算法
图算法 (最短路径，线性和分配，最小费用流，最大流)
路径规划问题(TSP,VRP)

or-tools的主要特性

开源免费
持续维护，改进和开发 Alive
详细的文档，提供 C++, Python, Java 和 C# 方面的示例
便捷，可以在以下平台编译：
- Ubuntu 14.04 and 16.04 up (64-bit).
- Mac OS X El Capitan with Xcode 7.x (64 bit).
- Microsoft Windows with Visual Studio 2013 and 2015 (64-bit)
高效
用户友好
良好测试

or-tools 结构介绍

目录	功能
algorithms	其他or-tools库使用的一些辅助算法
base	or-tools使用的基本utilities
constraint_solver	约束求解器
flatzinc	用于处理FlatZinc的实用程序
graph	Google的图和处理流问题的库
linear_solver	线性求解器(for linear programming)
lp_data	用于处理数据的线性优化问题的实用utilities
sat	Google的可满足性求解器
util	or-tools使用的通用utilities

or-tools 求解vrp问题示例

tsp问题求解

求解问题步骤：

1.准备数据: 给定若干个城市和他们之间的距离

[[   0, 2451,  713, 1018, 1631, 1374, 2408,  213, 2571,  875] , # New York
  [2451,    0, 1745, 1524,  831, 1240,  959, 2596,  403, 1589], # Los Angeles
  [ 713, 1745,    0,  355,  920,  803, 1737,  851, 1858,  262], # Chicago
  [1018, 1524,  355,    0,  700,  862, 1395, 1123, 1584,  466], # Minneapolis
  [1631,  831,  920,  700,    0,  663, 1021, 1769,  949,  796], # Denver
  [1374, 1240,  803,  862,  663,    0, 1681, 1551, 1765,  547], # Dallas
  [2408,  959, 1737, 1395, 1021, 1681,    0, 2493,  678, 1724], # Seattle
  [ 213, 2596,  851, 1123, 1769, 1551, 2493,    0, 2699, 1038], # Boston
  [2571,  403, 1858, 1584,  949, 1765,  678, 2699,    0, 1744], # San Francisco
  [ 875, 1589,  262,  466,  796,  547, 1724, 1038, 1744,    0]] # St. Louis

2.构造求解器

 # Cities
 city_names = ["New York", "Los Angeles", "Chicago", "Minneapolis", "Denver",
                "Dallas", "Seattle", "Boston", "San Francisco", "St. Louis"]
   tsp_size = len(city_names)
 # Create routing model
 if tsp_size > 0:
   # TSP of size tsp_size
   # Second argument = 1 to build a single tour (it's a TSP).
   # Nodes are indexed from 0 to tsp_size - 1. By default the start of
   # the route is node 0.
   routing = pywrapcp.RoutingModel(tsp_size, 1)
   search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
   # Setting first solution heuristic: the
   # method for finding a first solution to the problem.
   search_parameters.first_solution_strategy = (
       routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
   # Create the distance callback, which takes two arguments 
#(the from and to node indices)
   # and returns the distance between these nodes.
   dist_between_nodes = CreateDistanceCallback()
   dist_callback = dist_between_nodes.Distance
   routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

3.准备callback函数及完成整个程序

callback: a function that takes any pair of nodes in the graph for the problem and returns the distance between them — and then passes it to the solver

class CreateDistanceCallback(object):
  """Create callback to calculate distances between points."""
  def __init__(self):
    """Array of distances between points."""
    self.matrix = 
 [[   0, 2451,  713, 1018, 1631, 1374, 2408,  213, 2571,  875], # New York
  [2451,    0, 1745, 1524,  831, 1240,  959, 2596,  403, 1589], # Los Angeles
  [ 713, 1745,    0,  355,  920,  803, 1737,  851, 1858,  262], # Chicago
  [1018, 1524,  355,    0,  700,  862, 1395, 1123, 1584,  466], # Minneapolis
  [1631,  831,  920,  700,    0,  663, 1021, 1769,  949,  796], # Denver
  [1374, 1240,  803,  862,  663,    0, 1681, 1551, 1765,  547], # Dallas
  [2408,  959, 1737, 1395, 1021, 1681,    0, 2493,  678, 1724], # Seattle
  [ 213, 2596,  851, 1123, 1769, 1551, 2493,    0, 2699, 1038], # Boston
  [2571,  403, 1858, 1584,  949, 1765,  678, 2699,    0, 1744], # San Francisco
  [ 875, 1589,  262,  466,  796,  547, 1724, 1038, 1744,    0]] # St. Louis
  def Distance(self, from_node, to_node):
    return self.matrix[from_node][to_node]

4.调用求解器

  # Solve, returns a solution if any.
  assignment = routing.SolveWithParameters(search_parameters)
  if assignment:
    # Solution cost.
    print "Total distance: " + str(assignment.ObjectiveValue()) + " miles\n"
    # Inspect solution.
    # Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
    route_number = 0
    index = routing.Start(route_number) 
 # Index of the variable for the starting node.
    route = ''
    while not routing.IsEnd(index):
      # Convert variable indices to node indices in the displayed route.
      route += str(city_names[routing.IndexToNode(index)]) + ' -> '
      index = assignment.Value(routing.NextVar(index))
    route += str(city_names[routing.IndexToNode(index)])
    print "Route:\n\n" + route
  else:
    print 'No solution found.'
else:
  print 'Specify an instance greater than 0.'

输出示例：

A depot must be specified, setting one at node 0
Total distance: 7293 miles
Route:
New York -> Boston -> Chicago -> Minneapolis -> Denver -> Seattle ->
San Francisco -> Phoenix -> Dallas -> St. Louis -> New York

vrp问题求解

与tsp相比，示例vrp程序加入了车辆的容量限制，同时调度多辆车完成规划问题。

1.准备数据，生成每个站点的位置跟其货物需求；定义距离调用函数

def create_data_array():
  locations = [[82, 76], [96, 44], [50, 5], [49, 8], [13, 7], [29, 89], [58, 30], 
               [14, 24], [12, 39], [3, 82], [5, 10], [98, 52], [84, 25], [61, 59], 
               [88, 51], [91, 2], [19, 32], [93, 3], [50, 93], [98, 14], [5, 42],
               [61, 62], [9, 97], [80, 55], [57, 69], [23, 15], [20, 70], [85, 60]]
  demands = [0, 19, 21, 6, 19, 7, 12, 16, 6, 16, 8, 14, 21, 16, 3, 22, 18,
             19, 1, 24, 8, 12, 4, 8, 24, 24, 2, 20]
  data = [locations, demands]
  return data

def distance(x1, y1, x2, y2):
    # Manhattan distance
    dist = abs(x1 - x2) + abs(y1 - y2)
    return dist
# Distance callback
class CreateDistanceCallback(object):
  """Create callback to calculate distances between points."""
  def __init__(self, locations):
    """Initialize distance array."""
    size = len(locations)
    self.matrix = {}
    for from_node in xrange(size):
      for to_node in xrange(size):
          # get x1,y1,x2,y2 from the data
          self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)
  def Distance(self, from_node, to_node):
    return self.matrix[from_node][to_node]

2.准备demand的调用函数

# Demand callback
class CreateDemandCallback(object):
  """Create callback to get demands at each location."""
  def __init__(self, demands):
    self.matrix = demands
  def Demand(self, from_node, to_node):
    return self.matrix[from_node]

3.将demand生成dimension加入模型

Routing problems involve quantities that accumulate along a vehicle’s route. In this example, such a quantity is demand — say, the weight or volume of a package that must be delivered. For every location where a vehicle stops along its route, the total demand on the vehicle increases by the demand at that location. (Other examples of these types of quantities are the distance a vehicle travels, or its travel time.)

The routing solver stores each quantity of this type in an object called a dimension. The dimension contains a callback for the quantity, along with related data and variables. You can add a dimension to a routing problem using the solver’s AddDimension method. The following code creates a dimension for the demand in this example.

# Put a callback to the demands.
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand
# Add a dimension for demand.
slack_max = 0
vehicle_capacity = 100
fix_start_cumul_to_zero = True
demand = "Demand"
routing.AddDimension(demands_callback, slack_max, vehicle_capacity,
                     fix_start_cumul_to_zero, demand)

AddDimension介绍:

// Methods to add dimensions to routes; dimensions represent quantities
// accumulated at nodes along the routes. They represent quantities such as
// weights or volumes carried along the route, or distance or times.
// Quantities at a node are represented by "cumul" variables and the increase
// or decrease of quantities between nodes are represented by "transit"
// variables. These variables are linked as follows:
// if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i)
// where slack is a positive slack variable (can represent waiting times for
// a time dimension).
// Setting the value of fix_start_cumul_to_zero to true will force the "cumul"
// variable of the start node of all vehicles to be equal to 0.
// Creates a dimension where the transit variable is constrained to be
// equal to evaluator(i, next(i)); 'slack_max' is the upper bound of the
// slack variable and 'capacity' is the upper bound of the cumul variables.
// 'name' is the name used to reference the dimension; this name is used to
// get cumul and transit variables from the routing model.
// Returns false if a dimension with the same name has already been created
// (and doesn't create the new dimension).
// Takes ownership of the callback 'evaluator'.
bool AddDimension(NodeEvaluator2* evaluator, int64 slack_max, int64 capacity,
                  bool fix_start_cumul_to_zero, const std::string& name);

4.调用求解器

# Solve, displays a solution if any.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
  # Display solution.
  # Solution cost.
  print "Total distance of all routes:" +str(assignment.ObjectiveValue()) + "\n"
# 输出Routing结果

输出示例：

Total distance of all routes: 970
Route for vehicle 0:
0 -> 14 -> 2 -> 3 -> 23 -> 4 -> 11 -> 28 -> 6 -> 26 -> 0
Distance of route 0: 300
Demand met by vehicle 0: 100
Route for vehicle 1:
0 -> 27 -> 24 -> 0
Distance of route 1: 78
Demand met by vehicle 1: 44

另一个例子(VRPTW):

1.准备数据

start_times =  [28842, 50891, 10351, 49370, 22553, 53131, 8908,
                56509, 54032, 10883, 60235, 46644, 35674, 30304,
                39950, 38297, 36273, 52108, 2333, 48986, 44552,
                31869, 38027, 5532, 57458, 51521, 11039, 31063,
                38781, 49169, 32833, 7392]
end_times = [46842, 68891, 28351, 67370, 40553, 71131, 26908,
             74509, 72032, 28883, 78235, 64644, 53674, 48304,
             57950, 56297, 54273, 70108, 20333, 66986, 62552,
             49869, 56027, 23532, 75458, 69521, 29039, 49063,
             56781, 67169, 50833, 25392]

在这个例子中，我们定义总的时间为服务时间+路上花费的时间，其中服务时间与每个站点所需货物量成正比，路上花费的时间跟站点间的距离成正比。

2.定义callback函数

# Service time (proportional to demand) callback.
class CreateServiceTimeCallback(object):
  """Create callback to get time windows at each location."""
  def __init__(self, demands, time_per_demand_unit):
    self.matrix = demands
    self.time_per_demand_unit = time_per_demand_unit
  def ServiceTime(self, from_node, to_node):
    return self.matrix[from_node] * self.time_per_demand_unit

# Create the travel time callback (equals distance divided by speed).
class CreateTravelTimeCallback(object):
  """Create callback to get travel times between locations."""
  def __init__(self, dist_callback, speed):
    self.dist_callback = dist_callback
    self.speed = speed
  def TravelTime(self, from_node, to_node):
    travel_time = self.dist_callback(from_node, to_node) / self.speed
    return travel_time

# Create total_time callback (equals service time plus travel time).
class CreateTotalTimeCallback(object):
  """Create callback to get total times between locations."""
  def __init__(self, service_time_callback, travel_time_callback):
    self.service_time_callback = service_time_callback
    self.travel_time_callback = travel_time_callback
  def TotalTime(self, from_node, to_node):
    service_time = self.service_time_callback(from_node, to_node)
    travel_time = self.travel_time_callback(from_node, to_node)
    return service_time + travel_time

3.加入时间维度

# Add time dimension.
time_per_demand_unit = 300
horizon = 24 * 3600
time = "Time"
speed = 10
service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
service_time_callback = service_times.ServiceTime
travel_times = CreateTravelTimeCallback(dist_callback, speed)
travel_time_callback = travel_times.TravelTime
total_times = CreateTotalTimeCallback(service_time_callback, travel_time_callback)
total_time_callback = total_times.TotalTime
routing.AddDimension(total_time_callback,  # total time function callback
                     horizon,
                     horizon,
                     fix_start_cumul_to_zero,
                     time)

The significant inputs to the AddDimension method are the following:

total_time_callback — Returns the service time plus travel time to the next location.
horizon — An upper bound for the accumulated time over each vehicle’s route. This sets a global time window of [0, horizon] for all locations. To set the individual time windows at each location, you need to set ranges on the cumulative variable for time, as shown in Add time window constraints.
fix_start_cumul_to_zero — Since the value is True, the cumulative variable for time is set to 0 at the start of each vehicle’s route.
time — The name of the dimension, which you can use to access data or variables stored in it.

4.加入时间维度的限制

获取该dimension

1	time_dimension = routing.GetDimensionOrDie(time)

为其中的每个站点设置开始、结束时间值

for location in range(1, num_locations):
	start = start_time[location]
	end = end_time[location]
	time_dimension.CmulVar(location).SetRange(start, end)

3.3 使用到的相关代码

3.4 关键变量、函数与API

1.求解相关

初始解生成算法routing_first_solution
- default : select the first node with an unbound successor and connect it to the first available node
- GlobalCheapestArc :iteratively connect two nodes which produce the cheapest route segment
- LocalCheapestArc:select the first node with an unbound successor and connect it to the node which produces the cheapest route segment
- PathCheapestArc :starting from a route “start” node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route
search过程：
- Meta-heuristics启发式算法策略
  - routing_guided_local_search (default: false): activates guided local search (cf. http://en.wikipedia.org/wiki/Guided_Local_Search);
    this is generally the most efficient metaheuristic for vehicle routing;
  - routing_simulated_annealing (default: false): activates simulated annealing (cf. http://en.wikipedia.org/wiki/Simulated_annealing);
  - routing_tabu_search (default: false): activates tabu search (cf. http://en.wikipedia.org/wiki/Tabu_search).
- Local search neighborhoods
  - routing_no_lns (default: false): 使用LNS，可能会找到更好的解法，不过通常比较慢
    
    forbids the use of Large Neighborhood Search (LNS); LNS can find good solutions but is usually very slow.
    Refer to the description of PATHLNS in the LocalSearchOperators enum
    in constraint_solver.h for more information.
  - routing_no_tsp (default: true): 在求解当前模型时不使用精确算法求解“子”TSP问题
    
    forbids the use of exact methods to solve “sub”-traveling salesman problems (TSPs) of the current model (such as sub-parts of a route, or one route in a multiple route problem). Uses dynamic programming to solve such TSPs with a maximum size (in number of nodes) up to cp_local_search_tsp_opt_size (flag with a default value of 13 nodes). It is not activated by default because it can slow down the search.
- searching for solution 限制
  - routing_solution_limit (default: kint64max) 在找到若干次更好的解后停止
  - routing_time_limit (default: kint64max) 在查找若干时间后停止

2.Routing相关

有两类重要变量：

路径相关的变量
- next(i) i节点的直接后继的节点号；可以通过IndexToNode()得到该节点
- vehicle(i) 返回该节点属于车辆路径的编号
Dimension相关的变量
- dimension变量
- cumul(i, d) dimension为d的节点i的累积值
- transit(i, d) dimension为d的节点i的delta值

3.关键API

RoutingModel RoutingModel (int nodes, int vehicles, NodeIndex depot) : 构造VRP问题
const Assignment* RoutingModel :: SolveWithParameters (const RoutingSearchParameters& search_parameters)：求解VRP问题
void SetArcCostEvaluatorOfAllVehicles(NodeEvaluator2* evaluator)：定义最小化变量问题
VRP问题：加入若干节点属于同一辆车的约束：void AddSoftSameVehicleConstraint(const std::vector& nodes, int64 cost);
示例：solver->AddSoftSameVehicleConstraint();
标注数组中的节点应该分到同一辆车上，如果没在同一辆车上，每多一个特例，总成本函数增加cost.

VRP问题：加入两个节点存在接送关系：void AddPickupAndDelivery(NodeIndex node1, NodeIndex node2);满足：
1.node1,node2由同一辆车服务；
2.node1在node2前被访问。
使用示例:

//     Solver* const solver = routing.solver();
//     solver->AddConstraint(solver->MakeEquality(
//         routing.VehicleVar(routing.NodeToIndex(node1)),
//         routing.VehicleVar(routing.NodeToIndex(node2))));
//     solver->AddPickupAndDelivery(node1, node2);

AddDimension():

evaluator: 加入限制变量的callback函数
相关的两个变量： cumul(累加变量) transit(站点变量)
if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i)
capacity: cumul变量的最大值

fix_start_cumul_to_zero:开始时是否置为0

bool AddDimension(NodeEvaluator2* evaluator,
                 int64 slack_max, 
                 int64 capacity,
                 bool fix_start_cumul_to_zero,
                 const std::string& name
                );

自定义条件：在constraint_solver中加入constraint。示例:

 // b == (v == c)
Constraint* MakeIsEqualCstCt(IntExpr* const v, int64 c, IntVar* const b);
// status var of (v == c)
IntVar* MakeIsEqualCstVar(IntExpr* const var, int64 value);
// b == (v1 == v2)
Constraint* MakeIsEqualCt(IntExpr* const v1, IntExpr* v2, IntVar* const b);
// status var of (v1 == v2)
IntVar* MakeIsEqualVar(IntExpr* const var, IntExpr* v2);
// left == right
Constraint* MakeEquality(IntExpr* const left, IntExpr* const right);
// expr == value
Constraint* MakeEquality(IntExpr* const expr, int64 value);
// expr == value
Constraint* MakeEquality(IntExpr* const expr, int value);
// b == (v != c)
Constraint* MakeIsDifferentCstCt(IntExpr* const v, int64 c, IntVar* const b);
// status var of (v != c)
IntVar* MakeIsDifferentCstVar(IntExpr* const v, int64 c);
// status var of (v1 != v2)
IntVar* MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2);
// b == (v1 != v2)
Constraint* MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
                              IntVar* const b);
// left != right
Constraint* MakeNonEquality(IntExpr* const left, IntExpr* const right);
// expr != value
Constraint* MakeNonEquality(IntExpr* const expr, int64 value);
// expr != value
Constraint* MakeNonEquality(IntExpr* const expr, int value);
// b == (v <= c)
Constraint* MakeIsLessOrEqualCstCt(IntExpr* const v, int64 c,
                                   IntVar* const b);
// status var of (v <= c)
IntVar* MakeIsLessOrEqualCstVar(IntExpr* const v, int64 c);
// status var of (left <= right)
IntVar* MakeIsLessOrEqualVar(IntExpr* const left, IntExpr* const right);
// b == (left <= right)
Constraint* MakeIsLessOrEqualCt(IntExpr* const left, IntExpr* const right,
                                IntVar* const b);
// left <= right
Constraint* MakeLessOrEqual(IntExpr* const left, IntExpr* const right);
// expr <= value
Constraint* MakeLessOrEqual(IntExpr* const expr, int64 value);
// expr <= value
Constraint* MakeLessOrEqual(IntExpr* const expr, int value);
// b == (v >= c)
Constraint* MakeIsGreaterOrEqualCstCt(IntExpr* const v, int64 c,
                                      IntVar* const b);
// status var of (v >= c)
IntVar* MakeIsGreaterOrEqualCstVar(IntExpr* const v, int64 c);
// status var of (left >= right)
IntVar* MakeIsGreaterOrEqualVar(IntExpr* const left, IntExpr* const right);
// b == (left >= right)
Constraint* MakeIsGreaterOrEqualCt(IntExpr* const left, IntExpr* const right,
                                   IntVar* const b);
// left >= right
Constraint* MakeGreaterOrEqual(IntExpr* const left, IntExpr* const right);
// expr >= value
Constraint* MakeGreaterOrEqual(IntExpr* const expr, int64 value);
// expr >= value
Constraint* MakeGreaterOrEqual(IntExpr* const expr, int value);
// b == (v > c)
Constraint* MakeIsGreaterCstCt(IntExpr* const v, int64 c, IntVar* const b);
// status var of (v > c)
IntVar* MakeIsGreaterCstVar(IntExpr* const v, int64 c);
// status var of (left > right)
IntVar* MakeIsGreaterVar(IntExpr* const left, IntExpr* const right);
// b == (left > right)
Constraint* MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
                            IntVar* const b);
// left > right
Constraint* MakeGreater(IntExpr* const left, IntExpr* const right);
// expr > value
Constraint* MakeGreater(IntExpr* const expr, int64 value);
// expr > value
Constraint* MakeGreater(IntExpr* const expr, int value);
// b == (v < c)
Constraint* MakeIsLessCstCt(IntExpr* const v, int64 c, IntVar* const b);
// status var of (v < c)
IntVar* MakeIsLessCstVar(IntExpr* const v, int64 c);
// status var of (left < right)
IntVar* MakeIsLessVar(IntExpr* const left, IntExpr* const right);
// b == (left < right)
Constraint* MakeIsLessCt(IntExpr* const left, IntExpr* const right,
                         IntVar* const b);
// left < right
Constraint* MakeLess(IntExpr* const left, IntExpr* const right);
// expr < value
Constraint* MakeLess(IntExpr* const expr, int64 value);
// expr < value
Constraint* MakeLess(IntExpr* const expr, int value);

Quantities at a node are represented by “cumul” variables and the increase or decrease of quantities between nodes are represented by “transit” variables. These variables are linked as follows: if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i)

整理PPT：or_tool.pptx

Reference

https://en.wikipedia.org/wiki/Travelling_salesman_problem
https://en.wikipedia.org/wiki/Vehicle_routing_problem
https://developers.google.com/optimization/reference/constraint_solver/routing/
https://acrogenesis.com/or-tools/documentation/documentation_hub.html#user_manual
https://developers.google.com/optimization/
https://developers.google.com/optimization/routing/tsp/tsp
https://developers.google.com/optimization/routing/tsp/vehicle_routing_time_windows
https://github.com/google/or-tools/blob/master/src/constraint_solver/routing.h