Visit given city before a given cumulative distance in the traveling salesman problem

I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there a way to do this? My question is related to this unanswered CS question.

I have a mixed integer program using the R package CVXR that find the shortest route without subroutes (see below). The city order is represent in the vector node_order. The strategy I’ve pursued so far is:

  1. Re-organize node_order so that the index is the order and the value is the city id
  2. Look up the associated distances in distances
  3. Compute a vector with the cumulative sum of these distances.
  4. Add the constraint that city i must occur before the first index in (3) exceeding the distance constraint for that city.

The issues I’ve encountered with this approach is that I have not found a way to include finding-index-by-value into the optimization in CVXR. This is needed in both step (1) and (4) above. Maybe this is possible after all, or there is another approach? I am willing to use other packages than CVXR and other software than R.


My current program:

library(CVXR)  # Make distances N = 10 distances = matrix(1:(N*N), ncol = N)  # Flag 1 iff we travel that path. 0 otherwise do_transition = Variable(N, N, boolean = TRUE)  # Minimize the total duration of the traveled paths. objective = Minimize(sum(do_transition * distances))  # Only go one tour. Order is 1:(N-1) node_order = Variable(N-1, integer = TRUE) ii = t(node_order %*% matrix(1, ncol = N - 1))  # repeat as N rows jj = node_order %*% matrix(1, ncol = N - 1)  # repeat as N cols   # Constraints constraints = list(   do_transition * diag(N) == 0,  # Disallow transitions to self (diagonal elements)   sum_entries(do_transition, 1) == rep(1, N),  # Exactly one entrance to each node   sum_entries(do_transition, 2) == rep(1, N),  # Exactly one exit from each node   (jj - ii) + N * do_transition[2:N, 2:N] <= N - 1,  # One tour constraint (no subtours)   node_order >= 1,   # This interval represents order as ranks (1 to N-1)   node_order <= N-1 )  # Find optimum solution = solve(Problem(objective, constraints)) 

A bit of code pertaining to my current (unsuccessful) attempts:

# Get tour order #tour = order(c(NA, result$  getValue(node_order)))  # R solution tour = rep(NA, N-1) tour[result$  getValue(node_order)] = 2:N  # Get tour distances distances_optim = diag(distances[tour, tour[2:N]])  # Tour cumulative distances distances_cumul = cumsum_axis(distances_optim)