1st place, tie: Gabriel Homsi for his paper “Dynamic and Stochastic Rematching for Ridesharing Systems: Formulations and Reductions”

In this work, we study a dynamic and stochastic rematching problem with applications in ridesharing systems. In this problem, requests are received over time and correspond to the intent of engaging in ridesharing for a certain itinerary. Requests are associated with either a driver or a rider and are represented as nodes in a bipartite graph. The edges between requests represent feasible matches, that is, matches that have compatible time windows and that generate distance savings. Requests can be matched for a profit proportional to the amount of distance savings associated with the rideshare. Additionally, requests that are currently matched can be unmatched for a certain cost. Unmatching requests may be desirable if better match options become available over time. Decisions are taken under a rolling horizon framework, and profits and costs may also be time-dependent. The objective of the problem is to match and unmatch requests such that the net profit is maximized over the planning horizon. To solve this problem, we propose three mathematical programming formulations: a static formulation, a myopic formulation, and a two-stage stochastic formulation. Due to the possibly large number of time periods and scenarios in these formulations, they may be challenging to solve. To address this, we show that these formulations can be reduced provided that some simple and realistic conditions are met. In some cases, these formulations can be reduced to problems with only two time periods.

1st place, tie: Jørgen Skålnes for his paper “A new formulation for the inventory routing problem”

We propose a new general formulation for the inventory routing problem with a corresponding branch-and-cut algorithm. In this problem each customer has an inventory with a maximum inventory capacity and a periodic demand. The decision maker must make sure that the customers have enough products in their inventories to satisfy demand in each time period of the planning horizon. Thus, the decision maker must decide which customers to serve in which time periods, how much to deliver of a product once a customer is visited and how to route the fleet of vehicles in order to minimize transportation cost and inventory holding cost. We propose a new formulation based on customer schedules that is equally good as the state-of-the-art instance specific reformulation. However, the new formulation can handle varying demand and is not dependent on the maximum inventory levels to be a multiple of demand. Customer schedules contain information about delivery periods for each customer and quantity delivered to a given customer in each period. Customer visits, quantity delivered and inventory levels can all be expressed by convex combinations of customer schedules resulting in a tighter linear relaxation. We show that the new formulation is more general and that it performs equally good as the instance specific reformulation on the hardest benchmark instances, but at the cost of slightly slower node processing time.

2nd place: Peyman Kafaei for his paper “Deep Q-learning for simultaneous Beam Orientation and trajectory optimization for Cyberknife”

Optimizing radiation therapy treatment planning has been studied extensively. However, there is a dearth of studies for the CyberKnife which delivers high precision dose towards the tumor. The lengthy treatment deliveries results in discomfort and inadvertent movements of the patient which can drastically reduce the quality of the treatment and endanger the patient. Observations reveal that the robotic arm movements between nodes (beams) around the patient takes more than 70% of the treatment time; therefore, selecting the optimal set of beams such that the quality is almost maintained is highly beneficial. Formulating the Beam Orientation Optimization as a Combinatorial Optimization problem leads to a highly nonconvex and complex problem which is shown to be NP-hard. Thus, we opt for the Deep Q-learning to select the favorable beams. We explore different geometrical and radiobiological beam quality measures that incorporate individual patient characteristics. The proposed algorithm demonstrates substantial improvements in treatment time while maintaining the quality of the plan.

3rd place: Nazgol Niroumandrad for her paper “A Reinforcement Tabu Search Algorithm”

Meta-heuristic algorithms are widely known and chosen to solve many combinatorial problems. Over the last years a large number of algorithms were presented in which they combine various methods, sometimes from other optimization algorithms and outside of meta-heuristic fields, to improve the performance of meta-heuristics. The main idea of this research revolves around considering that meta-heuristics can behave more intelligent. In this research project, we are studying the effects of employing learning algorithms to improve the performance of a tabu search algorithm. Having a better exploration of the search space with exploring the solutions that are not reachable without these learning algorithms, leads to making them more efficient and reducing the computation time in complex problems. Due to this, we are studying a novel learning tabu search algorithm using learning methods in the context of a scheduling problem. We aim to use the benefit of reinforcement learning methods during the search and exploring into more promising regions which leads to enhance the performance of tabu search algorithm. The idea was inspired by the work of Samorani et al. (2018), in which they employed the K-means clustering in an iterative process for the path-relinking method. Experiments are conducted and show the benefit of using a learning mechanism under deterministic conditions. Samorani, M., Wang, Y., Lv, Z., Glover, F.: Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem. Journal of Heuristics pp. 1–14 (2018)

Honorable mention: Tayeb Mhamedi for his paper “A Branch-Price-and-cut algorithm for the two echelon vehicle routing problem with time windows”

We address the two-echelon vehicle routing problem with time windows (2E-VRPTW). In the 2E-VRPTW, first echelon routes handle transportation of goods from depots to intermediate facilities (satellites) while second echelon routes, departing from satellites, ensure that goods are being shipped to customers within their allowed time windows. Moreover, freight distributed by a second echelon route must be supplied from exactly one first echelon route. First, we propose a branch-price-and-cut algorithm to solve the 2E-VRPTW within which first echelon routes are added a priori into the formulation while second echelon routes are generated dynamically throughout the resolution process. Second, we take advantage of information on the dual optimal solution space to derive deep dual-optimal inequalities (DDOI) to stabilize the overall column generation process. Third, we introduce valid inequalities that improve the quality of the dual bounds. Finally, we report computational results obtained on instances from the literature with up to 100 customers and 5 satellites that we are able to solve to optimality.