Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

R.P.C.M. Apulia (Reconstructing Prehistoric Communities’ Mobility in Apulia)

The research originates in the necessity to bring a new systematic archaeological perspective to the prehistoric background of northern Apulia. Therefore, the aim of the R.P.C.M. Apulia project is to shed new light on a specific chronological arch, from the Neolithic to Early Bronze Age, of the northern part of the Apulia, because the related studies resulted updated to the 70-80’s with some sporadic exception. Moreover, addressing the investigation to the relationship between the communities and the landscape, so how they could exploit the lands and how they could move into this area keeping in touch. To reconstruct the Prehistorical dynamics, it has been necessary first of all to create a database containing all the information about the sites thus to validate them and classifying them according to a model specifically built. The storing operation has been conducted with the software ArcGIS v.10.1 and the sites have been georeferenced on the map as points. It provided the basis on which developing the analysis concerning the mobility (Least Cost Path) and landscape perception (Fuzzy Viewshed Analysis). The first one has been considered to evaluate the mobility into the study area. Therefore, to generate sample paths on the base of the time in reaching a specific point and the terrain trend. The gained information has been collected to hypothesize how they could keep in touch across the chronological changes for purposes related to trading/idea/people exchanges. The visibility analysis has been led to grasp how the groups perceived the landscape through the sight. This datum covered an important role, especially from the Copper Age, concerning the domain and control of the trading ways. The data coming from the mentioned analysis have been used to read into the settlement choices according to the development of the new socio-economic relationships and plan survey activity.