> Primary Team ID: 17
> Secondary Team ID: 34

## Abstract

Vehicle routing is an important problem in the logistics industry, particularly for last-mile hubs. These hubs are responsible for delivering goods to customers in a specific area, and they need to optimize their routes in order to minimize costs and maximize efficiency. One key aspect of vehicle routing is capturing the accurate weight of the goods to be delivered. This is important because it affects the amount of fuel required for each trip, as well as the capacity of the vehicle. Additionally, if the weight of the goods is not accurately captured, it can lead to delays and other issues in the delivery process

This report summerises our approach to solving the dyanamic varient of the vehicle routing problem with pickups and deliveries considered in the Inter IIT Tech Meet 11.0. In what follows, we will describe our appraoch to tackle this problem with techniques from Operatino Reasech and Machine learning. Our current solver is a mixture of the most succesful experiments we have run so far. We also showcase current web and app framework and design. We highlight our appraoch and setup to accuretly predict voluemteric and dead weight of the items provided.

## Methodology and Approach

### Volume Estimation from images

In this study, we propose a method for estimating the volume and mass of an object using computer vision techniques. To estimate the volume, we capture images of any two adjacent faces of the object against a clear background, which includes a reference object (a 2cm x 2cm black square in our case) to compare the dimensions of the object with and obtain the absolute values of the object. By taking one image of one face of the object and repeating the process with an adjacent face, we are able to obtain all three dimensions, and thus the total volume of the object.

For the task of dead-weight estimation, we employ deep learning models which take as input an image of the object alongside the dimensions estimated above and output an estimated value of the mass. Our method primarily uses two Xception neural networks in tandem to obtain an approximate density map and geometry of the object, and finally combining both to estimate the mass of the object.

This method requires minimal infrastructure and can be set up in a matter of a couple of minutes, reducing the initial costs. It is also quick and effective, as we require only two images from a simple smartphone camera and inference can be performed on a smartphone, enabling easy usage by warehouse staff and minimal training requirements. Additionally, the use of deep learning models allows for a high level of accuracy and robustness in the estimation of mass.


### Vechicle Routing

We experimented with various methods and architechtures to solve this problem. Our current approach is based on Hybrid Genetic Search (HGS).

Hybrid Genetic Search (HGS) is a metaheuristic approach that combines elements of genetic algorithms (GA) and heuristic search methods.The algorithm begins by generating a set of initial solutions, or routes, using a combination of random initialization and heuristic construction methods. The fitness of each solution is calculated according to a fitness function that takes into account both the cost of the individual route and its contribution to diversity within the population. This preservation of diversity is crucial for the algorithm's performance.Education is then applied to the solutions, with a probability of applying a neighborhood search to the solutions. This education is not restricted to random mutations, but rather intelligent heuristics are used to improve the solutions. The best solutions, or routes, are then selected from the population based on their fitness and used to generate the next generation of routes. Different types of crossovers, such as OX and SREX, are used to generate new solutions. In our implementation, we utilized the SREX crossover method.

In order to improve the performance of the Hybrid Genetic Search (HGS) algorithm, several optimizations were added:
1. Local Search Caching: To avoid unnecessary neighborhood evaluations of unchanged routes, Wouter et al. [2] proposed an efficient local search caching mechanism that keeps track of route modifications during local search. Our approach extends this mechanism to track route changes outside the local search. This optimization has been shown to improve performance in practice, as the selective route exchange operator tends to modify only a small subset of routes.
2. Improving Diversity and Crossover: In order to preserve diversity and explore the full search space, our approach implements a parent selection mechanism that balances diversity and crossover. When the offspring solutions are too similar, they do not offer any significant new information to the population while on the other hand, randomly cross-breeding solutions often results in offspring that are unstable or ineffective. Keeping in mind that we have to go at the edge of our search space where the bag capacity or the maximum route size has just exceeded the constaints as best solutions have high probability of existing on the boundary of feasibility and infeasibility. We implement this by selecting the first parent by a binary tournament, then when selecting the second we impose a constraint on the diversity. In particular, a constraint is imposed on the percentage of broken edge pairs between the two parents: this percentage needs to be between some lower and upper bounds _divl_, _divu_. Tuning suggests divl = 10% and divu = 50% are effective.
3. Better Education: Our approach applies a better education method during local searches, by using the SWAP neighborhood. This neighborhood is based on the traditional 2-opt neighborhood, which is widely used in VRP, but it also considers the pickup and delivery constraints of the VRPPD. The SWAP* neighborhood allows for the exchange of customers between routes while maintaining feasibility by ensuring that the pickup and delivery constraints are not violated. This allows the algorithm to explore a larger solution space and find better solutions.


In addition to the Hybrid Genetic Search (HGS) algorithm, we are also exploring other approaches to solve the problem. Two of these approaches include the Variable Neighbourhood Search (VNS) Metaheuristic algorithm and the Iterated Fast ILS Localized Optimization (I-FILO) algorithm.

In VNS algorithm we start by calculating an initial routing solution using the Best-Fit Decreasing Demand (BFDD) heuristic. Next, we apply local optimization techniques to the solution, followed by gradually increasing the neighborhood size and performing a random shuffling of the existing routing solution. The process is then repeated, with another round of local optimization applied to the newly shuffled solution. The local optimization techniques applied include both reversing segments and exchanging segments between two routes to optimize the total distance travelled.

The I-FILO algorithm is an iterated local optimization algorithm that combines two different search strategies: forward search and inverse search. The forward search is used to improve the quality of the solutions by applying local optimization techniques to the current solution, while the inverse search is used to escape from local optima and explore new regions of the solution space. The forward search is similar to other local search techniques such as FILO or the search phase of HGS. In the inverse search phase, the algorithm applies inverse optimization techniques such as the inverse exchange operator to the current solution. The inverse exchange operator swaps the positions of two customers in different routes, regardless of their feasibility. The goal of the inverse search is to escape from local optima and explore new regions of the solution space.

These alternative approaches offer new perspectives and techniques for solving the vehicle routing problem and can be used to enhance the performance of the HGS algorithm or in some cases provide better results.

For the dynamic pickups we are working on a ML based approach. The idea is to decide on a set of requests to postone and dispatch and then solving a VRP on the set of dispatched requestes. The idea is that for any set of requests, there exists a prize vector θt such that including only those requests where the detour is smaller than the prize collected by serving them equals the optimal dispatched routes. The approach reduces the problem of learning to make binary decisions to predicting prizes, and the optimization problem to the well-known PCVRPTW, a variant of the VRPTW that drops customer covering constraints and instead pays a request-specific prize θv for each served request v.

The pipeline consists of two layers: the prediction layer (φw) and the combinatorial optimization layer (f). The prediction layer uses machine learning to predict the cost of serving a request in a later epoch. The combinatorial optimization layer constructs and solves a PCVRPTW instance using the predicted costs as request prizes.

## Deployement

## Future Improvements