2017/05/23 by Renatha Capua, Yuri Frota, Capua, Renatha +5 · 1 citation
Decision Sciences · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1705.08495
openalex publication_date 2017/05/23 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We propose an iterated local search based on several classes of local and\nlarge neighborhoods for the bin packing problem with conflicts. This problem,\nwhich combines the characteristics of both bin packing and vertex coloring,\narises in various application contexts such as logistics and transportation,\ntimetabling, and resource allocation for cloud computing. We introduce O(1)\nevaluation procedures for classical local-search moves, polynomial variants of\nejection chains and assignment neighborhoods, an adaptive set covering-based\nneighborhood, and finally a controlled use of 0-cost moves to further diversify\nthe search. The overall method produces solutions of good quality on the\nclassical benchmark instances and scales very well with an increase of problem\nsize. Extensive computational experiments are conducted to measure the\nrespective contribution of each proposed neighborhood. In particular, the\n0-cost moves and the large neighborhood based on set covering contribute very\nsignificantly to the search. Several research perspectives are open in relation\nto possible hybridizations with other state-of-the-art mathematical programming\nheuristics for this problem.\n