Scheduling Transportation Events with Grouping Genetic Algorithms and the Heuristic DJD

摘要

Grouping problems arise in many applications, and the aim is to partition a set U of items, into a collection of mutually disjoint subsets or groups. The objective of grouping is to optimize a cost function such as to minimize the number of groups. Problems in this category may come from many different domains such as graph coloring, bin packing, cutting stock, and scheduling. This investigation is related in particular to scheduling transportation events, modeled as a grouping problem, and with the objective to minimize the number of vehicles used and satisfying the customer demand. There is a set of events to be scheduled (items) into a set of vehicles (groups). Of course, there are constraints that forbid assigning all events to a single vehicle. Two different techniques are used in this work to tackle the problem: Grouping Genetic Algorithms and an algorithm based on the heuristic DJD widely used for solving bin packing problems. Both methods were adapted to the problem and compared to each other using a set of randomly generated problem instances designed to comply with real situations.