Imagine many jobs with work loads and time windows located in a city. These jobs need wi-fi provided by dynamic emitters, i.e. mobile coverage vehicles, which have a limited coverage radius and can stop anywhere on the map. There exists one depot where both job vehicles (transporting people to job locations) and mobile coverage vehicles can leave and come back. How should job and coverage vehicles travel so that their total distance is minimized, and all jobs are performed with wi-fi access?

To my knowledge, despite the wide research performed in vehicle routing problems, including vehicle routing problems with time windows, our problem constitutes a novel direction. It combines coordinated routing with joint optimization. As cities' ICT infrastructure grows, the need for on-the-go task completion, particularly for emergency vehicles and the military, increases; through this project, we lay the foundation for such work.

The first formulation is called the direct formulation (DF), which distills potential routes into arcs between location nodes for both job and coverage locations and vehicles. An optimizer is called on this mixed-integer program. It is slow, but does produce the exact best answer. An improvement is to use set-partitioning, which lists all routes possible from job vehicles and optimizes minimum cost by considering all these routes. This is also slow, but it is an improvement on DF time-wise. Here, consideration temporarily switches from joint (jobs and coverage together) optimization to jobs-only optimization, as the problem is a standard vehicle routing with time windows.

I used column generation (CG) to solve the jobs-only problem. Instead of enumerating all routes, I only consider a small set of initial routes which I know are feasible. Then, I feed them into the restricted master problem (RMP), which is the same as the set partitioning solution, except with far fewer routes. Then, extracting the dual variables and solving a subproblem generates the single best new route not yet included in the RMP. The loop repeats until no new route with negative reduced cost can be found.

The innovation in CG is realizing that the subproblem is actually a shortest paths problem, solvable through Bellman-Ford. The equation in the dual that must be violated to generate a better route can be computed through a graph traversal. There are a few strategic variables that need to be considered, such as how to represent the new route; I chose to do so as a set of nodes and arrival/departure times, along with their reduced costs.

During CG, we relied on a set of y-decision variables to inform us when work was being performed at a job location. I mathematically proved that this was unnecessary by showing that if we are at a node, we should be doing work, otherwise we possibly worsen the objective. By removing y-decision variables and combining this with a reduced-cost-pruning insight from Prof. Jacquillat, we doubled our CG frontier from solving 35 routes in 10 minutes to solving 74 routes in 4 minutes.

After blazing through the jobs-only algorithm using CG, it was time to confront the two-stage problem, which combines job routes and coverage routes simultaneously. I proposed a "double column generation" (DCG) algorithm, which treats the entire system as one large CG problem and follows the same routine as the jobs-only CG. One of the most important steps was my proving that only a very limited set of times were worth exploring in graph traversal on coverage routes, dramatically reducing the time taken to solve DCG.

Warm starts - solving jobs-only and/or coverage-only to generate a set of "great" routes for input to DCG - accelerated the process further. A final acceleration technique came through the sparsity of a dual variable. For coverage routes in the subproblem, we want to find routes with negative reduced cost, which could only be achieved if the dual variable xi associated with certain nodes is highly positive. However, the vast majority of xi's are zero. Rather than wasting Bellman-Ford on so many non-positive xi's, I invented a "treasure-hunting" algorithm which only uses "golden intervals" containing at least one non-zero xi.

Through these acceleration methods, the algorithm solved in 4 minutes for 50 jobs, rather than the 2 hours 22 minutes it took through the direct formulation benchmark - a reduction of 96.3%. I presented our research to Singapore's Defense Science and Technology Agency (DSTA) in September, and published a paper on arXiv.