Conference Agenda

Advancements in computer hardware technology and commercial-purpose software have paved the way for leveraging branch-and-cut methodologies to address medium-scale vehicle routing problems (VRPs). Despite the introduction of efficient heuristics in the literature, tailoring these approaches to suit various VRP variants remains a challenge. In this study, we explore the potential of combining branch-and-cut techniques with constrained k-means clustering.

Our work focuses on a Matheuristic approach that integrates branch-and-cut methods with constrained k-means clustering. We achieve this by decomposing the original VRP into subproblems using constrained k-means clustering, where the clustering assignment subproblem is reformulated as a minimum-cost flow linear network optimisation problem.

Our methodology begins by decomposing the customers into geographical-based clusters, thereby imposing the manageable size for the subproblems and facilitating efficient application of branch-and-cut techniques. Subsequently, these subproblems are solved iteratively to derive a comprehensive solution. To improve the final solution obtained, we conduct cross-validation through rigorous back testing. We demonstrate the effectiveness of our approach on known benchmark instances of VRPs with time windows and compare it with state-of-the-art solutions. Our result shows that the approach achieves comparable or better performance for up to 400 customers.

Digital 3D objects find extensive application across various industries, notably in manufacturing. Within the realm of generating 3D computer images, cubic graphs hold particular significance despite posing challenges in hardware implementation. A notable approach to alleviate this challenge involves reducing triangles into a single strip, which notably eases hardware processing. Achieving such a single strip alignment corresponds to solving the Hamiltonian cycle problem (HCP) in the dual graph. Notably, branch-and-bound methodologies are essential in tackling constraint satisfaction problems like the HCP. Recent studies underscore the efficacy of adaptive branching strategies over fixed schedules. This research introduces a novel branching strategy focused on maximizing fixed arcs within the Hamiltonian cycle, comparing its effectiveness against other established methods in the field.

As part of a practical student project at RWTH Aachen University, we looked at the problem of how large parcel service providers manage the huge volumes of parcels that have to be transported between different sorting centers every day.

When transporting the swap bodies that contain the parcels, a fine balance must be struck between low transport costs and timely delivery to the destination. Furthermore, the sorting centers are subject to a limited throughput, i.e., the number of parcels that can be processed per hour, which must be respected.

As part of this project, the key question of how to optimize the routing of transport containers between locations while ensuring that many shipments can be delivered the next day had to be answered. Because the project has only just started at the beginning of the semester, we are very excited to find out which of the various models and algorithmic approaches will result in the best outcome possible, and we are looking forward to sharing our findings with you!

The proximity to resource and customer locations is among the most important criteria in site selection for manufacturing companies. For many applications, e.g., in the area of circular economy, companies have to bear the responsibility of collecting resources. In such scenarios, their operational planning involves the selection of resource markets as well as the generation of resource collection and customer delivery routes. While the Location-Routing Problem (LRP) integrates the facility location and customer delivery routing, there is a lack of integrated approaches that additionally take resource collection routes into account. Recognizing this need for a comprehensive approach, we introduce a novel integer mathematical programming model, the Location-Routing Problem with Resource Collection and Customer Delivery (LRP-RCCD). By integrating the LRP with the Multi-Depot Traveling Purchaser Problem (MDTPP), the LRP-RCCD minimizes operational and transportation costs while meeting customer demands. This unified framework allows for the simultaneous optimization of location decisions, resource selection, resource collection routes, and customer delivery routes. We consider multiple resource types, each of which is available from multiple markets with heterogeneous prices, making efficient resource selection and collection routing crucial. To investigate the value of an integrated modeling of resource collection and customer delivery routes, we conduct computational experiments using exemplary test instances. We compare the results of considering only customer routes with simplified direct resource collection in site selection with those obtained using our integrated LRP-RCCD formulation.