Cookies
O website necessita de alguns cookies e outros recursos semelhantes para funcionar. Caso o permita, o INESC TEC irá utilizar cookies para recolher dados sobre as suas visitas, contribuindo, assim, para estatísticas agregadas que permitem melhorar o nosso serviço. Ver mais
Aceitar Rejeitar
  • Menu
Publicações

Publicações por CEGI

2024

Heuristics for online three-dimensional packing problems and algorithm selection framework for semi-online with full look-ahead

Autores
Ali, S; Ramos, AG; Carravilla, MA; Oliveira, JF;

Publicação
APPLIED SOFT COMPUTING

Abstract
In online three-dimensional packing problems (3D-PPs), unlike offline problems, items arrive sequentially and require immediate packing decisions without any information about the quantities and sizes of the items to come. Heuristic methods are of great importance in solving online problems to find good solutions in a reasonable amount of time. However, the literature on heuristics for online problems is sparse. As our first contribution, we developed a pool of heuristics applicable to online 3D-PPs with complementary performance on different sets of instances. Computational results showed that in terms of the number of used bins, in all problem instances, at least one of our heuristics had a better or equal performance compared to existing heuristics in the literature. The developed heuristics are also fully applicable to an intermediate class between offline and online problems, referred to in this paper as a specific type of semi-online with full look-ahead, which has several practical applications. In this class, as in offline problems, complete information about all items is known in advance (i.e., full look-ahead); however, due to time or space constraints, as in online problems, items should be packed immediately in the order of their arrival. As our second contribution, we presented an algorithm selection framework, building on developed heuristics and utilizing prior information about items in this specific class of problems. We used supervised machine learning techniques to find the relationship between the features of problem instances and the performance of heuristics and to build a prediction model. The results indicate an 88% accuracy in predicting (identifying) the most promising heuristic(s) for solving any new instance from this class of problems.

2024

Estimating Alighting Stops and Transfers from AFC Data: The Case Study of Porto

Autores
Hora, J; Ferreira, MC; Camanho, A; Galvão, T;

Publicação
Lecture Notes in Networks and Systems

Abstract
This study estimates alighting stops and transfers from entry-only Automatic Fare Collection (AFC) data. The methodology adopted includes two main steps: an implementation of the Trip Chaining Method (TCM) to estimate the alighting stops from AFC records and the subsequent application of criteria for the identification of transfers. For each pair of consecutive AFC records on the same smart card, a transfer is identified considering a threshold for the walking distance, a threshold for the time required to perform an activity, and the validation of different boarding routes. This methodology was applied to the case study of Porto, Portugal, considering all trips performed by a set of 19999 smart cards over one year. The results of this methodology allied with visualization techniques allowed to study Origin-Destination (OD) patterns by type of day, seasonally, and by user frequency, each analyzed at the stop level and at the geographic area level. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

2024

Pallets delivery: Two matheuristics for combined loading and routing

Autores
Silva, E; Ramos, AG; Moura, A;

Publicação
EXPERT SYSTEMS WITH APPLICATIONS

Abstract
The implementation of novel regulatory and technical requirements for the distribution of vehicle axle weights in road freight transport introduces a new set of constraints on vehicle routing. Until now, axle weight distribution in determining the load plan for freight transport units has been overlooked in the vehicle routing process. Compliance with these axle weight constraints has become paramount for road freight transport companies, since noncompliance with the axle weight distribution legislation translates into heavy fines. This work aims to provide a tool capable of generating cargo loading plans and routing sequences for a palletised cargo distribution problem. The problem addressed integrates the capacitated vehicle routing problem with time window and the two-dimensional loading problem with load balance constraints. Two integrative solution approaches are proposed, one giving greater importance to the routing and the other prioritising the loading. In addition, a novel MILP model is proposed for the 2D pallet loading problem with load-balance constraints that take advantage of the standard dimension of the pallets. Extensive computational experiments were performed with a set of well-known literature benchmark instances, extended to incorporate additional features. The computational results show the effectiveness of the proposed approaches.

2024

Synchronisation in vehicle routing: Classification schema, modelling framework and literature review

Autores
Soares, R; Marques, A; Amorim, P; Parragh, SN;

Publicação
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

Abstract
The practical relevance and challenging nature of the Vehicle Routing Problem (VRP) have motivated the Operations Research community to consider different practical requirements and problem variants throughout the years. However, businesses still face increasingly specific and complex transportation re-quirements that need to be tackled, one of them being synchronisation. No literature contextualises syn-chronisation among other types of problem aspects of the VRP, increasing ambiguity in the nomenclature used by the community. The contributions of this paper originate from a literature review and are three-fold. First, new conceptual and classification schemas are proposed to analyse literature and re-organise different interdependencies that arise in routing decisions. Secondly, a modelling framework is presented based on the proposed schemas. Finally, an extensive literature review identifies future research gaps and opportunities in the field of VRPs with synchronisation.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )

2024

The drone-assisted vehicle routing problem with robot stations

Autores
Morim, A; Campuzano, G; Amorim, P; Mes, M; Lalla-Ruiz, E;

Publicação
EXPERT SYSTEMS WITH APPLICATIONS

Abstract
Following the widespread interest of both the scientific community and companies in using autonomous vehicles to perform deliveries, we propose the 'Drone-Assisted Vehicle Routing Problem with Robot Stations' (VRPD-RS), a problem that combines two concepts studied in the autonomous vehicles literature: truck-drone tandems and robot stations. We model the VRPD-RS as a mixed-integer linear program (MILP) for two different objectives, the makespan and operational costs, and analyze the impact of adding trucks, drones, and robots to the delivery fleet. Given the computational complexity of the problem, we propose a General Variable Neighborhood Search (GVNS) metaheuristic to solve more realistic instances within reasonable computational times. Results show that, for small instances of 10 customers, where the solver obtains optimal solutions for almost all cases, the GVNS presents solutions with gaps of 0.7% to the solver for the makespan objective and gaps of 0.0% for the operational costs variant. For instances of up to 50 customers, the GVNS presents improvements of 21.5% for the makespan objective and 8.0% for the operational costs variant. Furthermore, we compare the GVNS with a Simulated Annealing (SA) metaheuristic, showing that the GVNS outperforms the SA for the whole set of instances and in more efficient computational times. Accordingly, the results highlight that including an additional drone in a truck-drone tandem increases delivery speed alongside a reduction in operational costs. Moreover, robot stations proved to be a useful delivery element as they were activated in almost every studied scenario.

2024

Learning efficient in-store picking strategies to reduce customer encounters in omnichannel retail

Autores
Neves-Moreira, F; Amorim, P;

Publicação
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS

Abstract
Omnichannel retailers are reinventing stores to meet the growing demand of the online channel. Several retailers now use stores as supporting distribution centers to offer quicker Buy-Online-Pickup-In-Store (BOPS) and Ship-From-Store (SFS) services. They resort to in-store picking to serve online orders using existing assets. However, in-store picking operations require picker carts traveling through store aisles, competing for store space, and possibly harming the offline customer experience. To learn picking policies that acknowledge interactions between pickers and offline customers, we formalize a new problem called Dynamic In-store Picker Routing Problem (diPRP). This problem considers a picker that tries to pick online orders (seeking) while minimizing customer encounters (hiding) - preserving the offline customer experience. We model the problem as a Markov Decision Process (MDP) and solve it using a hybrid solution approach comprising mathematical programming and reinforcement learning components. Computational experiments on synthetic instances suggest that the algorithm converges to efficient policies. We apply our solution approach in the context of a large European retailer to assess the proposed policies regarding the number of orders picked and customers encountered. The learned policies are also tested in six different retail settings, demonstrating the flexibility of the proposed approach. Our work suggests that retailers should be able to scale the in-store picking of online orders without jeopardizing the experience of offline customers. The policies learned using the proposed solution approach reduced the number of customer encounters by up to 50%, compared to policies solely focused on picking orders. Thus, to pursue omnichannel strategies that adequately trade-off operational efficiency and customer experience, retailers cannot rely on actual simplistic picking strategies, such as choosing the shortest possible route.

  • 1
  • 158