Data-driven Inverse Optimization (IO) is a form of Supervised Learning where it is assumed that the output data is found by means of an optimization problem that depends on the input data. IO uses this data to approximate the optimization problem as best as possible. In the case where one wants to emulate an expert operating in a dynamic environment, the dataset obtained by measuring the expert is often contained in a small, optimal part of the total state space of the environment. When a model trained on this data finds itself in a different part of the state space, it can behave erratically.
In this thesis, we will combine Inverse Optimization with the active learning method of Dataset Aggregation (DAgger) to test if this improves model performance in dynamic settings. DAgger is an iterative process where the system is steered by the learner, creating new input data for the expert to find the best actions. This new data is then used to train a new model.
Furthermore, we propose a new algorithm, fast-DAgger, that should converge faster than the DAgger algorithm, at the possible cost of performance in the final model.
IO models trained with the DAgger and fast-DAgger algorithms are tested and compared to IO models trained on static datasets. This is done for two case studies: the Dynamic Vehicle Routing Problem as proposed by the EURO meets Neurips 2022 Vehicle Routing Competition, and the game of Tetris.
Results show the potential of combining IO with DAgger. However, DAgger is not always better than training with a static dataset. DAgger can only be helpful when the static training data is limited to a part of the total state space and when this data does not generalize well to the total state space. The fast-DAgger algorithm did not show a significant speed-up compared to the normal DAgger algorithm in the case studies. However, this is very dependent on the specifics of the model and the hyperparameters of the DAgger algorithm.
... Read more

Logistics and mobility services play a major role in our society, and efficient routing is a crucial part of this. However, even though routing problems have been widely researched, the solutions provided by algorithms do not always match drivers' expectations. Routing costs used by these algorithms are often based on one or a few parameters, but in real-world operations, many factors and sometimes hard-to-define aspects are responsible for this. Drivers can consider these different aspects and some studies found that experienced drivers often plan better delivery routes than the optimization tools. In this research, we focus on using expert decision data as examples for learning the costs of routing and train a policy that can make decisions more in line with the expectations of the expert. We formulate state-action representations for the TSP and CVRP, which we use to interpret these routing problems as inverse optimization and multiclass classification problems. Additionally, we propose multiple policy training approaches as well as state feature vector transformations that can be used based on the characteristics of the routing problems. These different training configurations are utilized to train different existing algorithms with training data sets consisting of example state-action pairs. The performance of the trained models is compared to each other and the optimal solution. The optimal solution acted as expert example and was used to create the training data. We demonstrate that both inverse optimization and multiclass classification algorithms are able to imitate expert decision-making for new problem instances from example data. However, we also show a large variation in performance depending on the problem, state features, algorithm formulations and training configuration. ... Read more

Optimizing delivery routes is a well-researched topic, however, most of the classical approaches do not incorporate preferences of drivers, as those approaches focus on minimizing the time or distance of the routes. As a result, the actual driven route of an experienced driver often deviates from the proposed route since the drivers have tacit knowledge about the real-life conditions of the road network. Amazon proposed a challenge to learn a delivery route planning strategy from historically driven routes and thus incorporate this tacit knowledge.
In this thesis, we will tackle the challenge using data-driven inverse optimization to learn the zone sequencing patterns of drivers. The zone sequences of expert drivers are assumed to be the solutions to a traveling salesman problem (TSP) in which the weights represent the preference of a driver to use a certain edge. The values of the weights will be learned through inverse optimization. Our final approach achieves a score that ranks 4th out of the 48 models that qualified for the final round of the challenge. ... Read more