（1）建模的思想

本节仍然采取和10.1.2中类似的网络流思想建立数学模型。假设有一个流量为n-1的流进入网络，该网络流沿着一条路径流经网络中的某些点和边，每经过一个点就被吸收掉一个单位的流量，没有被吸收掉的流均进入终点。

（2）建模步骤

给定图G=（V，E），其中V={v₁，v₂，…v_n}，且v₁为起点，v_n为终点；

τ_i表示在v_i点完成服务所需要的时间，主要包括两部分，在v_i点完成服务的基本时间和等待服务的时间，前者与到达v_i的时刻无关，后者则依赖于到达v_i的时刻，若用y_i表示旅行者达到v_i点的时刻，则τ_i=τ_i0+f（y_i）；

（w₁，w₂，…，w_n）为收益向量，w_i表示在v_i点完成服务所能获得的收益；

S⊂V为指定点集，即必须为其服务的点的集合。(www.daowen.com)

定义模型的决策变量

f_ij表示流过（v_i，v_j）边的流量；

y_i表示旅行者达到v_i点的时刻，如果没有经过v_i点，则y_i=0。

带指定点集和时间依赖型定向问题可以表示成如下的整数规划模型

上述整数规划模型的含义如下：目标函数表示访问过的点对应的总收益最大，约束条件（10-15）表示从v₁点出发，约束条件（10-16）表示最终回到v_n点，约束条件（10-17）表示其余点均是路径的中间点的备选点，约束条件（10-18）表示指定点集中的所有点必须包含在路径中，约束条件（10-19）和（10-20）表示如果有非零流量经过某条边则该边必包含在路径中，否则该边一定不包含在路径中，约束条件（10-21）是经过路径中的每一个中间点的流量平衡约束，即从中间点流出的总流量等于流入的总流量减去被该点吸收的流量，其中每一个包含在路径中的点恰好吸收掉一个单位的流量，约束条件（10-22）表示进入网络的总流量为n-1，该约束可以保证路径中的点不超过n个，约束条件（10-23）是为每个点的服务时间与到达该点的时刻之间的关系，约束条件（10-24）表示从起点出发的时刻为0，约束条件（10-25）表示回到终点的时刻不超过其最晚时间T_max，约束条件（10-26）表示连续访问的两个点的到达时刻之间的关系，即到达后一点的时刻等于到达前一个点的时刻加上在前一个点的服务时间和走在路上的时间，约束条件（10-27）表示没有访问过的点到达时刻为0，约束条件（10-28）是变量取值约束。

本节中的模型与10.1节中的模型唯一不同的约束是式（10-23），式（10-23）中τ_i是变量而不是常量，若式（10-23）是线性约束，则该模型也是整数线性规划模型。