Master thesis - New Algorithmic Approaches for Large-Scale Fleet-Size and Mix-Vehicle Routing

Job description

Transport is at the core of modern society. Imagine using your expertise to shape sustainable transport and infrastructure solutions for the future? If you seek to make a difference on a global scale, working with next-gen technologies and the sharpest collaborative teams, then we could be a perfect match. 

 

Location: Göteborg/Host University/Volvo GTT
Time Schedule : Jan – June 2025 

The heavy-duty vehicle sector contributes over 25% of greenhouse gas emissions from road transport in the EU while only accounting for roughly 2% of the vehicles on road [1].  We believe battery-electric vehicles (BEVs) are crucial in reducing our climate footprint. However, the electrification of commercial heavy vehicles introduces new challenges in operational, infrastructure, route, and investment planning for our customers. 

Summary:
In this thesis, we focus on computational investigations into algorithms for current state-of-the-art mixed fleet vehicle routing problem with pickup and delivery demand. Several problem-specific side constraints will be shared with the students and hence, a new approach must be investigated. We have accurate energy, range, and fleet planning algorithms and aim to further enhance these approaches. The goal is to create a new algorithmic method that improves the computational performance of our existing algorithms on real-world benchmarking instances. Students will have the chance to contribute to our codebase and potentially co-author a scientific journal or conference paper. They will work closely with our team of Ph.D. s and experienced researchers in Vehicle Engineering, Applied Mechanics, Mathematics, Statistics, Vehicle Dynamics.

Theoretical  background: The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem that, despite extensive research, continues to evolve with the emergence of new variants. Due to the problem being NP-Hard, no polynomial-time algorithms exist that can efficiently solve it in all cases. As the problem size scales, the time to solve the problem increases exponentially, making solving to near-optimality computationally prohibitive for large instances. 

There is research effort made generally in two directions: Exact approaches such as column generation (Branch and Price and cut [2], [3]), constraint programming ( [4]), Lagrangian relaxation (sub-gradient optimization [5]), Benders’ decomposition ( [6]). On the other hand, inexact approaches such as metaheuristics ( [7]), math-heuristic [8]), and recently deep-reinforcement learning algorithm ( [9]) have proven to be very effective for large-scale problems often performing well in many international VRP competitions [10]. Our aim is to integrate both areas with a focus on practical computational strategies, considering real-world constraints in hardware and software.

Skills necessary: Some courses in optimization and linear algebra. Understanding of Python/C++, some Github/Git, and any one of the popular MILP solvers. ML/AI skills are good to have.

Planned activities: Students will first study the existing optimization codebase. Next, they'll perform a literature review, exploring recent scientific contributions and relevant open-source tools. Then, they'll develop and test methods on benchmark instances. 

Total Number of Students: 2

Contacts: 
Toheed Ghandriz, Ph.D.
toheed.ghandriz@volvo.com
Sunney Fotedar, Ph.D.
sunney.fotedar@consultant.volvo.com

Please send in your application by the  17th of November.

Bibliography

·  "Heavy Duty Vehicles: Council signs off on stricter co2 emission standards," European Union, 2024. [Online]. Available: https://www.consilium.europa.eu/en/press/press-releases/2024/05/13/heavy-duty-vehicles-council-signs-off-on-stricter-co2-emission-standards/.
·  G. Desaulniers, "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Transportation Science, vol. 58, no. 1, 2009. 
·  I. Muter, J.-F. Cordeau and G. Laporte, "A Branch-and-Price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes," Transportation Science, vol. 48, no. 3, 2014. 
·  K. Booth and J. Beck, "A Constraint Programming Approach to Electric Vehicle Routing with Time Windows.," in CPAIOR 2019, 2019. 
·  B. Kallehauge, J. Larsen and O. B.G. Madsen, "Lagrangian duality applied to the vehicle routing problem with time windows," Computers and Operations Research, vol. 33, no. 5, 2006. 
·  R. F. Fachini and V. A. Armentano, "Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows," Computers and Industrial Engineering, vol. 148, 2020. 
·  D. Pisinger and S. Ropke, "A general heuristic for vehicle routing problems," Computers and Operations Research, vol. 34, no. 8, pp. 2403-2435, 2007. 
·  C. Archetti and M. Speranza, "A survey on matheuristics for routing problems," EURo Journal on Computational Optimization, vol. 2, no. 4, pp. 223-246, 2014. 
·  J. Kallestad, R. Hasibi, A. Hemmati and K. Sörensen, "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, vol. 309, no. 1, pp. 446-468, 2023. 
·  EURO, "VeRoLog Solver Challange," EURO, 2024. [Online]. Available: https://www.euro-online.org/websites/verolog/verolog-solver-challenge/.

We value your data privacy and therefore do not accept applications via mail. 

 

Who we are and what we believe in 
Our focus on Inclusion, Diversity, and Equity allows each of us the opportunity to bring our full authentic self to work and thrive by providing a safe and supportive environment, free of harassment and discrimination. We are committed to removing the barriers to entry, which is why we ask that even if you feel you may not meet every qualification on the job description, please apply and let us decide.

 

Applying to this job offers you the opportunity to join Volvo Group. Every day, across the globe, our trucks, buses, engines, construction equipment, financial services, and solutions make modern life possible. We are almost 100,000 people empowered to shape the future landscape of efficient, safe and sustainable transport solutions. Fulfilling our mission creates countless career opportunities for talents with sharp minds and passion across the group’s leading brands and entities. 

 

Group Trucks Technology are seeking talents to help design sustainable transportation solutions for the future. As part of our team, you’ll help us by engineering exciting next-gen technologies and contribute to projects that determine new, sustainable solutions. Bring your love of developing systems, working collaboratively, and your advanced skills to a place where you can make an impact. Join our design shift that leaves society in good shape for the next generation.

Job Category:  Technology Engineering

Organization:  Group Trucks Technology

Travel Required:  No Travel Required

Requisition ID:  14584