Treball guanyador de la XXI Edició dels premis a Treballs de Recerca de la UdL per a l’estudiantat de batxillerat i cicles formatius de grau superior en l'Àrea Tecnològica. Tutora: Vanessa Florenza Royes (Vedruna Balaguer de Balaguer (Lleida)).
This research project creates a web page where delivery businesses can plan an optimal route for distributing their packages to customers. This feat is achieved by a Python, HTML and CSS program which allows users to input several desired destinations, whose distances between them are calculated thanks to a Google Sheets document with a Google Maps connection to give specific data. When all information has been gathered, it is run through a variation of the Held-Karp algorithm. Created back in the 1960s, it has the ability to return the shortest route going through every point just once. The algorithm considers the distances and destinations as a weighted graph, a combination of nodes and edges joining them with different values (often understood as their distance, such as in this case). Afterwards, the graph is divided into small groups to get the shortest path from each. Finally, the graph is rejoined by adding each node according to the results collected during the subdivision step, and the outcome is obtained. The previous process, coded with Python language, is materialized as a list stating the final order and the total distance, as well as a map representing the route itself with an HTML and CSS part, a common tool for web programming. Apart from the efficiency benefits gained from route optimization, an analysis is performed to test the profitability of using electrical vehicles for delivery. This is made with real data from a local delivery company whose routes span all across the Spanish province of Lleida. First, the program scans the optimal path for each of the company’s itineraries to check whether they could be done with an electrical van. After confirming these vehicles could only make four out of six possible routes due to autonomy issues, an economical study was done to see how much time it would take to earn a profit from electrical vans if they were used instead of fuel ones, turning out to be more than thirteen years total, making them unworthy for the business. In conclusion, this research joins the branches of computer science and economics to learn that nowadays trying to improve delivery companies’ sustainability by avoiding traditional vehicles is an unprofitable task and states some changes, such as an autonomy increase or an improvement in electrical motors’ efficiency, should be made to revert this situation.