Browsing by Subject "time windows"

Now showing 1 - 3 of 3

Access status: Open Access ,
An assignment heuristic for time-dependent periodic routing problems with complex constraints
(AGH University of Science and Technology Press, 2020) Śliwiński, Tomasz
Periodic routing and scheduling is of the utmost importance in many industries with mobile personnel working in the field: sales representatives, service technicians, suppliers, etc. In many cases, the long-term stability of the customer to salesman assignment is required, leading to the decomposition of the major problem into single salesman subproblems. The paper addresses the assignment of customers to salesmen for the future services performed in a periodic fashion. It can be seen as the decomposition phase of the periodic vehicle routing problem PVRP into a number of Periodic Traveling Salesman Problems (PTSP). The proposed algorithm seeks the best assignment by taking into account diverse system requirements, constraints and expected operational costs including time windows, time-dependent travel times and costs, and labor laws.
Access status: Open Access ,
Multi-objective optimization of vehicle routing problem using evolutionary algorithm with memory
(Wydawnictwa AGH, 2017) Podlaski, Krzysztof; Wiatrowski, Grzegorz
The idea of a new evolutionary algorithm with memory aspect included is proposed to find multiobjective optimized solution of vehicle routing problem with time windows. This algorithm uses population of agents that individually search for optimal solutions. The agent memory incorporates the process of learning from the experience of each individual agent as well as from the experience of the population. This algorithm uses crossover operation to define agents evolution. In the paper we choose as a base the Best Cost Route Crossover (BCRC) operator. This operator is well suited for VPRTW problems. However it does not treat both of parent symmetrically what is not natural for general evolutionary processes. The part of the paper is devoted to find an extension of the BCRC operator in order to improve inheritance of chromosomes from both of parents. Thus, the proposed evolutionary algorithm is implemented with use of two crossover operators: BCRC and its extended-modified version. We analyze the results obtained from both versions applied to Solomon’s and Gehring & Homberger instances. We conclude that the proposed method with modified version of BCRC operator gives statistically better results than those obtained using original BCRC. It seems that evolutionary algorithm with memory and modification of Best Cost Route Crossover Operator lead to very promising results when compared to the ones presented in the literature.
Access status: Open Access ,
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych
(Wydawnictwa AGH, 2005) Giaro, Krzysztof; Kubale, Marek
In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.