An Optimisation engine for clustering points and generating optimal routes
Report Bug
·
Request Feature
Table of Contents
This repository contains our solution for tackling the Optimisation Problem, which consists of Clustering the delivery points, generating optimal routes and calculating the bin packing.
We receive the data about the items to be delivered from our database which consist some basic information about the item and it's delivery location. From this we first try to cluster the items based on their location, through which each cluster will be assigned to a single driver for delivery. After clustering the delivery locations together, we try to find the most optimised path among the points taking into consideration the Estimated Delivery Times, Weather and Traffic so as to improve customer experience with on time deliveries. To make it easy for the delivery rider as well, we provide a efficient bag packing for the delivery bag so as to save time and effort for the driver to search for package at the time of delivery.
All the algorithms used in our solution are then ensembled together to get the best result among all the possible combinations. Metrics are calculated among the combinations to get the maximum score. The best is then used for final execution. This data is then sent to the front-end to show it to the user.
In addition to all this, we also provide a service for dynamic addition of pickup points in the routes of a particular rider, leading into re-routing of the pre-determined path.
Execute the following commands to build and run the docker image lastmiledelivery/optimizer-server.
To pull image directly from docker-hub :
sudo docker pull lastmiledelivery/optimizer-server:latestTo run the docker image
sudo docker run -dp 5000:50051 optimizer-server:latestTo run the server -
sudo docker logs -f <CONTAINER-ID>The server is now ready to recieve requests at port number 5000 on your local system.
The api request format for the enpoint is given in the quick installation section below.
The Docker Image uses an Ensemble of all implemented algorithms mentioned above to output the best possible results for the given data. To test the algorithms individually, please install the codebase locally.
Details of the implemented algorithms is available under the Documentation section.
We specify detailed instructions on the required libraries and Dependencies needed to build and run the code. We recommend to use a Ubuntu 22.04 machine for all purposes.
$ sudo apt-get update
$ sudo apt-get install build-essential autoconf git pkg-config automake libtool curl make g++ unzip libcurl4-openssl-dev cmakeThis repository depends on mainly two external repositories:
- OR-tools
- gRPC
We install all libraries of OR-Tools and gRPC system-wide. Therefor both of them can be cloned and built anywhere in the system using the instructions given below.
To compile and install OR-Tools, we build it from source and install the generated libraries system-wide. Refer to [https://github.com/google/or-tools/blob/stable/cmake/README.md]. We used the following commands to fetch and build the repository
$ git clone -b main https://github.com/google/or-tools
$ cd or-tools
$ cmake -DCMAKE_CXX_STANDARD=17 -S. -Bbuild -DBUILD_DEPS:BOOL=ON
$ cd build
$ make -j 4
$ sudo make installgRPC is a modern open source high performance Remote Procedure Call (RPC) framework to connect different services. Refer to [https://github.com/grpc/grpc/blob/master/BUILDING.md] To clone and build the gRPC repository (v1.50.0), Use the following command:
$ git clone --recurse-submodules -b v1.50.0 \
--depth 1 --shallow-submodules https://github.com/grpc/grpc
$ cd grpc
$ mkdir -p cmake/build
$ cd ./cmake/build
$ cmake -DCMAKE_CXX_STANDARD=17 -DCMAKE_INSTALL_PREFIX=/usr/local \
-DCMAKE_POSITION_INDEPENDENT_CODE=TRUE -DABSL_PROPAGATE_CXX_STD=TRUE ../.. \
-DgRPC_INSTALL=ON \
-DCMAKE_BUILD_TYPE=Release \
-DgRPC_ABSL_PROVIDER=package \
-DgRPC_CARES_PROVIDER=module \
-DgRPC_PROTOBUF_PROVIDER=package \
-DgRPC_RE2_PROVIDER=package \
-DgRPC_SSL_PROVIDER=module \
-DgRPC_ZLIB_PROVIDER=package
$ make -j 4
$ sudo make installIn order to setup a local copy of the project, you can follow the one of the 2 methods listed below. Once the local copy is setup, the steps listed in Usage can be used to interact with the system.
Clonethe repo$ git clone https://github.com/Grow-Simplee-KGP/Optimiser
- Alternatively, Download a ZIP of the source code from github.
unzipfile to unpack all the files included with the project.$ unzip Optimiser-main.zip
- Change directory to the
Optimiserdirectory$ cd Optimiser - Create a build folder inside the
Optimiserdirectory and run cmake to generate the makefile. After running the make command, the executable is created in the
$ mkdir -p cmake/build
$ cd cmake/build
$ cmake ../..
$ make -j 4- To run the built binary, run the following command from the
Optimiserdirectory:
$ ./bin/serverBy default the server starts at port 50051 in the local machine.
Once the local copy of the project has been setup, follow these steps to interact with the system and run tests on the system
You can create a GRPC request containing the Warehouse location , maximum number of riders and list of packages.
The requests are to be structured according to the OptimiserRequest message format specified in proto/main.proto.
Given below is a sample request.json file. You can send this using any grpc client (we recommend postman client).
{
"packages": [
{
"id": 1,
"size": {"length": 4.24591402225247, "width": 5.52875984930662, "height": 5.7068272249847904},
"coordinates": {"latitude": 12916375, "longitude": 77649741},
"weight": 11.978200435741485
},
{
"id": 2,
"size": {"length": 15.69703671350186, "width": 14.797416561668777, "height": 7.423968512381623},
"coordinates": {"latitude": 12974678, "longitude": 77604902},
"weight": 10.81211662971237
},
{
"id": 3,
"size": {"length": 6.615859132172195, "width": 28.528347665831106, "height": 15.023585167751161},
"coordinates": {"latitude": 12972718, "longitude": 77635140},
"weight": 10.512273325983648
}
],
"bin": {"size": {"length": 80, "width": 80, "height": 80}, "capacity": 512000},
"riders": 15,
"warehouse": {"latitude": 12907009, "longitude": 77585678}
}
On sending the above request an OptimiserResponse message packet is obtained which lists all clusters and their routes along with packing position.
Given below is a sample response.
{
"clusters": [
{
"packages": [
{
"id": 2,
"position": {
"x": 0,
"y": 0,
"z": 0,
"length": 15,
"breadth": 14,
"height": 7
}
},
{
"id": 3,
"position": {
"x": 0,
"y": 0,
"z": 14,
"length": 28,
"breadth": 6,
"height": 15
}
},
{
"id": 1,
"position": {
"x": 15,
"y": 0,
"z": 0,
"length": 5,
"breadth": 4,
"height": 5
}
}
]
}
]The above response is the result of ensembling across all the algorithms mentioned in Acknowledgements section at the end of this document.
Instead of running the GRPC server, for quick and easy testing run the terminal application.
We currently support two testing methods:
-
Testing against custom input:
Run the following command$ ./bin/main <INPUT_FILENAME>.txt.The input file format is specified in
input_format.txtin source file. -
Testing against standard VRP Dataset to compare results with current optimal.
Download the VRP dataset from here. Then run the following command :$ ./bin/main <INPUT_FILE>.vrp
Here<INPUT_FILE>.vrpis the desired VRP input file.
Following are the details of the file structure of this project:
.
├── bin
│ └── server
├── include
│ ├── binpack
│ │ └── EB_AFIT.hpp
│ ├── clustering
│ │ ├── Clarke
│ │ ├── fesif
│ │ ├── HGS
│ │ ├── selfClustering
│ │ └── TimeWindow
│ ├── datastructures.hpp
│ ├── DistMatrix.hpp
│ ├── interface
│ │ ├── BinPackInterface.hpp
│ │ ├── ClusteringInterface.hpp
│ │ └── RoutePlanInterface.hpp
│ ├── routeplan
│ │ ├── TSP_CK.hpp
│ │ ├── TSP_LK.hpp
│ │ ├── TSP_OR_EDD.hpp
│ │ └── TSP_OR.hpp
│ └── Optimiser.hpp
├── lib
├── main.cpp
├── README.md
├── server.cpp
├── src
│ ├── binpack
│ │ └── EB-AFIT.cpp
│ ├── clustering
│ │ ├── Clarke
│ │ ├── fesif
│ │ ├── HGS
│ │ ├── selfClustering
│ │ └── TimeWindow
│ ├── DistMatrix.cpp
│ ├── Optimiser.cpp
│ └── routeplan
│ ├── TSP_CK.cpp
│ ├── TSP_DP.cpp
│ ├── TSP_LK.cpp
│ ├── TSP_OR.cpp
│ └── TSP_OR_EDD.cpp
├── tests
│ ├── data_gen.py
│ └── visualise_cluster.py
├── CMakeLists.txt
└── Dockerfile
Following are the details of the file structure and their functionalities that are present in this code base.
-
Optimiser/bin - This folder contains all the necessary binaries for running servers for all the GRPC calls.
Serverbinary - Starts the server through which the backend will interact with this code.
-
Optimiser/include/binpack - This folder contains all the header files used in the Optimiser code for bag packing.
EB_AFIT.hpp- Header file for the EB_AFIT algorithm implemented. It consist of all the functions required to run the algorithm in the Optimiser parallely.
-
Optimiser/include/clustering - This folder contains all the header files used in the Optimiser code for clustering of the location points.
Clarke- This folder contains all the header files required to implement the Enhanced Clarke-Wright Algorithm. More about the algorithm is present along with the cpp files of the same.fesif- This folder contains all the header files required to implement our fast FESI algorithm to get the clusters for further route planning.HGS- This folder contains all the header files reqiured to implement the Genetic algorithm we are using for clustering and path planning simultaneously. In this folder complete support for our HGS is present with tuned hyper-parameters for the best performance.selfClustering- The petal cut header files are present in this folder.TimeWindow- This folder contains header files for calculating thread metric and time window of each delivery, which is used to increase the percentage of on time deliveries.
-
Optimiser/include/datastructures.hpp - This folder contains all the data structure definions used in our code. This is done so as to formalise the data structure across all the algorithm, making it easier to ensemble the algorithm and minimise overhead to start each algorithm.
-
Optimiser/include/DistMatrix.hpp - The methods distance matrix calculation among different locations are present in this header file. The functions are made modular so as to provide easy access for extensions and in current work.
-
Optimiser/include/interface - This folder contains all the interfaces used in the optimiser, this made us to make a clean structure of code so as the code is easily maintainable and extensible. Each of the interface in this folder takes care of one important step of optimisation.
ClusteringInterface.hpp- All the clustering algorithms classes are extensions of this interface, a common function ComputeClusters is implemented in each of them to provide the clusters from the given location points.RoutePlanInterface.hpp- All the route planning algorithms are extensions of this interface, we take the benefit of different Object Oriented Principles in creating such a structure.BinPackInterface.hpp- This interface takes care of the Bag Packing part of our solution, all the algorithms implemented for the packing have used this interface.
-
Optimiser/include/routeplan - This folder contains header files for all the route planning algorithms. Here all the algorithms are trying to solve the Travelling Salesman Problem(TSP), as after clustering of locations our problem reduced to a basic TSP with addition constraints of EDD and capacity.
TSP_CK.hpp- This file consist of all the methods used in the modified Christofides algorithm for solving the TSP.TSP_LK.hpp- TSP solver using Lin-Kernighan has been implemented using this header file. This algorithm has been modified to incorporate the traffic data to get precise results for path planning and good approximation for achieving maximum EDDsTSP_OR_EDD.hpp- This header file uses the Google OR tools to get the path in each cluster, in addition to the basic OR tools solution we have also added metric to handle the constraints given in the problem statement to get the required results.
-
Optimiser/include/Optimiser.hpp - This header file is the heart of our solution. This handles the creation of ensemble among all the above algorithms and then provide the best results among all the combinations. Parallelism is used in this through threading to increase the speed among the algorithms.
-
Optimiser/lib - This folder consist of all the third party libraries such as Google OR tools and the GRPC header files to get the routing and connect backend with our algorithms respectively. These libraries are natively built so as to provide flexibility among the systems it is compiled on.
-
Optimiser/main.cpp - This file is the spine of our solution. This handles all the data inputs and the parallel running of the Optimiser class to get the best result among all. This file can be changed to test different algorithms and visulaise the results as well. This file will be similar to server.cpp
-
Optimiser/src/binpack - The older structure of the src folder is similar to what was in the header file, but this contains implementation of all the methods discussed above.
./binpackfolder consist of the binpacking algorithms implementation.EB-AFIT.cpp- The implementation of our modified Bin Packing algorithm which is based on the EB-AFIT algorithm[Bin Packing 2] is done in this file. In this we have added constraints to get the package at top at their respective delivery location.
-
Optimiser/src/clustering - All the clustering algorithms are implemented in this folder.
-
Clarke- As discussed in the include folder, this contains the implementation of our Clarke algorithm which is similar to [Clustering Algorithms 1]. Our algorithm is inspired by Kruskal's algorithm of finding the Minimum Spanning Tree, in which we first select the most profitable locations, profit being the cost reduced in traveling, and join them if they satisfy the condition of endpoints, i.e. the locations need to be the endpoints of their respective group. -
HGS- An extremely efficient randomization algorithm based on a meta-heuristic search on the Genetic Paradigm inculcating penaty costs on distance, cluster size and delay times of delivery based on a certain average speed of delivery. This algorithm generates a path for the cluster formed as well which is later further optimzed. It is a modified version of the algorithm described in [Clustering Algorithms 2]. -
fesif- 'fast Embedding Sorting and Insertion`[Clustering Algorithms 3] is a 6ρ Approximation Algorithm for package clustering implemented using a greedy approach - For a given “travel budget”, a binary search strategy is used to find the largest number of packages that can be delivered from the package list . A Hierarchical Search Tree is used as spatial index to embed the cost metric to minimize the delay in delivery time. -
selfClustering- Hours and hours of testing lead us to the realization that most of the clusters formed are "petal shaped". Thus we define two cuts - radial cut and angular cut to find the most optimal clusters formed by this "petal shaped" analogy. It is an extremely fast O(NlogN) algorithm to generate clusters.- Manhattan Distance
- Euclidean Distance
- Haversine Distance
- Real World Path Distance (Bing Maps API)
- Real World Path Time (Bing Maps API) All route plannning algorithms can thus use any of the above metric to compute optimal paths based on input format.
-
-
Optimiser/src/Optimser.cpp - Top Level of our System Design, which implements the complete pipleline starting from Clustering packages using the
Clustering Interfaceto Route Planning for riders using theRoute Planning Interfaceto finally ordering and Bin Packing using theBin Packing Interfaceto give the final optimized results, which supports an ensembled implementation, thus providing best possible results from all available algorithms. -
Optimiser/src/routeplan - This folder contains implementation of all route planning algorithms inheriting the Route Planning Interface. More formally, it contains all implemented variants of the Travelling Salesman Problem while handling additional constrained dimensions.
TSP_CK.cpp- An improved variant of the Christofides Algorithm [Routing Algorithms 1] which supports Estimated Delivery Time. It is an extremely efficient approximation algorithm for the Travelling Salesman problem which translates remarkably well in a real world setting.TSP_LK.cpp- Inspired from Lin Kernighan Algorithm [Route Planning Algorithm 3], we develop a modified heuristic based approach to which takes a tour (Hamiltonian cycle) as part of the input and attempts to improve it by searching in the neighbourhood of the given tour for one that is shortersolve the Travelling Salesman Problem.TSP_OR.cpp- An ensembled implementation of randomization and approximation algorithms from the linear programming library - OR-tools developed by google. Refer to [Routing Algorithms 2] for more details.TSP_OR_EDD.cpp- An implementation of Constrained Vehicle Routing Problem with an added constrained dimension of estimated time of delivery while minimizing package dropoffs.Refer to [Routing Algorithms 2] for more details.
Class Diagram
We experimented with various algorithms to solve the different components of the problem statement and found that different combinations of algorithms work best for different test cases. Therefore, we combined these components into an "Ensembler" object to achieve the best results.
The input is fed into the Ensembler, which creates multiple instances of the "Optimizer" class to work on the optimization problem concurrently. The final output is selected by polling the combination with the lowest cost.
Sequence Diagram
The Optimizer class creates interfaces for "ClusteringInterface," "BinPackInterface," and "RoutePlanInterface," which serve as the backend for different algorithms. The input is first passed to the ClusteringInterface, which provides the clusters. These clusters are then processed by both the RoutePlanInterface and BinPackInterface to determine the path, bin packing orientation, and corresponding costs. The lowest cost combination is then selected and its final output is used for further processing.
We list below any external resource we came across to help us build the entire codebase -
- Clarke Wright Algorithm - Improved upon the classical clarke wright algorithm to also handle
Estimated Time of Deliveryand added a consolidation function. - HGS - Hybrid Genetic Search -A Genetic Algorithm for the CVRP . Added
time expectationto get a better performing heuristic. - fESI - Fast Embedding Sorting and Insertion - A
6ρ Approximation Algorithmimplemented using a binary search strategy. A Hierarchical Search Tree is used as spatial index to embed the cost metric.
- Christofides Algorithm Industry Standard Approximation Algorithm for Travelling Salesman Problem.
- Google OR-Tools - Linear Programming Optimization library developed by Google with ensemble of randomization and approximation algorithm for CVRP.
- Lin Kernighan Algorithm - A Local Search based algorithm belonging to the family of combinatorial optimization to solve the Travelling Salesman Problem.
- Online 3D Bin Packing Using Algorithm - Trained RL agent for bin backing which maintains package ordering while packing.
- EB-AFIT - Algorithm for 3D Binpacking with an improved setup to maintain package ordering while having high bin packing efficiency.
- Google gRPC- RPC server handler for handling client side requests by Google.
- Bing MAPS API Accessable Microsoft API for computing real world distance matrices.
- redis GEOSEARCH Efficently finds the closest points using geohashing methods to identify candidtate points for dynamic pickup.