<jupyter_start><jupyter_text>The modelWith a few modifications, the original traveling salesman problem can support multiple salesman. Instead of making each facility only be visited once, the origin facility will be visited multiple times. If we have two salesman then the origin is visited exactly twice and so on.For **K** vehicles or sales people: Variables:$x_{ij}=\begin{cases}1: \text{the path goes from city i to j}\\0: \text{otherwise}\end{cases}$ order dummy variables:$u_i - u_j + C*x_{ij} \leq C - d_j, C = N/K$$\begin{cases}u_i: \text{order that site i is visited}\\d_j: \text{the cost to visit city j}, 0 \leq u_i \leq C - d_j, \forall i \in V \setminus \{0\}\end{cases}$ Goal:$min\sum_{i=0}^{n}\sum_{j\neq{i}, j=0}^{n}{c_{ij}}{x_{ij}}$$\begin{cases}c_{ij}: \text{distance from city i to city j}\\x_{ij}: \text{whether there's a path between i and j}\end{cases}$ Constraints:$\sum_{i\in{V}}{x_{ij} = 1}, \forall j \in V \setminus \{0\}$$\sum_{j\in{V}}{x_{ij} = 1}, \forall i \in V \setminus \{0\}$$\sum_{i\in{V}}{x_{i0} = K}$$\sum_{j\in{V}}{x_{0j} = K}$<jupyter_code>K = 4 #the number of sales people 
#create the problme
prob=LpProblem("vehicle", LpMinimize)
#indicator variable if site i is connected to site j in the tour
x = LpVariable.dicts('x',distances, 0,1,LpBinary)
#dummy vars to eliminate subtours
u = LpVariable.dicts('u', sites, 0, len(sites)-1, LpInteger)
#the objective
cost = lpSum([x[(i,j)]*distances[(i,j)] for (i,j) in distances])
prob+=cost
#constraints
for k in sites:
    cap = 1 if k != 'Berlin' else K
    #inbound connection
    prob+= lpSum([ x[(i,k)] for i in sites if (i,k) in x]) ==cap
    #outbound connection
    prob+=lpSum([ x[(k,i)] for i in sites if (k,i) in x]) ==cap
    
#subtour elimination
N=len(sites)/K
for i in sites:
    for j in sites:
        if i != j and (i != 'Berlin' and j!= 'Berlin') and (i,j) in x:
            prob += u[i] - u[j] <= (N)*(1-x[(i,j)]) - 1<jupyter_output><empty_output><jupyter_text>Solve it!<jupyter_code>%time prob.solve()
#prob.solve(GLPK_CMD(options=['--simplex']))
print(LpStatus[prob.status])
non_zero_edges = [ e for e in x if value(x[e]) != 0 ]

def get_next_site(parent):
    '''helper function to get the next edge'''
    edges = [e for e in non_zero_edges if e[0]==parent]
    for e in edges:
        non_zero_edges.remove(e)
    return edges
tours = get_next_site('Berlin')
tours = [ [e] for e in tours ]

for t in tours:
    while t[-1][1] !='Berlin':
        t.append(get_next_site(t[-1][1])[-1])<jupyter_output><empty_output><jupyter_text>The optimal route:<jupyter_code>for t in tours:
    print(' -> '.join([ a for a,b in t]+['Berlin']))<jupyter_output>Berlin -> Budapest -> Bucharest -> Istanbul -> Sofia -> Belgrade -> Vienna -> Berlin
Berlin -> Hamburg -> Dublin -> London -> Paris -> Brussels -> Berlin
Berlin -> Prague -> Rome -> Barcelona -> Madrid -> Milan -> Munich -> Berlin
Berlin -> Warsaw -> Kiev -> Moscow -> Saint Petersburg -> Stockholm -> Copenhagen -> Berlin<jupyter_text>Calculate total time:<jupyter_code>totalTime = 0;
for t in tours:
    time = 0
    for i in range(0, len(t)):
        time += flighttime.loc[t[i][0], t[i][1]]
#         print(flighttime.loc[t[i][0], t[i][1]])
#     print(time)
    if time > totalTime:
        totalTime = time
print(totalTime)
#draw the tours
colors = [np.random.rand(3) for i in range(len(tours))]
for t,c in zip(tours,colors):
    for a,b in t:
        p1,p2 = positions[a], positions[b]
        plt.plot([p1[0],p2[0]],[p1[1],p2[1]], color=c)

#draw the map again
for s in positions:
    p = positions[s]
    plt.plot(p[0],p[1],'o')
    plt.text(p[0]+.01,p[1],s,horizontalalignment='left',verticalalignment='center')
    
plt.title('%d '%K + 'people' if K > 1 else 'person')
plt.xlabel('latitude')
plt.ylabel('longitude')
# plt.gca().axis('off')
plt.show()
print('Longest time spent:', totalTime, '(min)')
print('Total distance:', value(prob.objective), '(km)')<jupyter_output>Longest time spent: 1988 (min)
Total distance: 15425.02 (km)
{'fraction_non_alphanumeric': 0.18077115673510266, 'fraction_numerical': 0.015773660490736103, 'mean_word_length': 4.082697201017812, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '259505', 'license': 'Apache-2.0', 'n_tokens_mistral': 1524, 'n_tokens_neox': 1464, 'n_words': 429, 'path': 'vehicle-routing-problem-master/vrp.ipynb', 'repo_name': 'huongquynh1611/Routing_optimization', 'size': '3994'}