An Assignment and Routing Problem With Time Windows and Capacity Restriction

Abstract

In under-developed or developing countries, the needs of indigent population are of a pressing nature most of the time. One of the objectives of municipal authorities is to collect donations and distribute the donated items and funds to indigent residents. This task requires a good matching of donations and needs for effectively meeting the needs of recipients. The distribution route is also important for time/cost-effective operations. This study presents a mixed integer programming model that integrates these matching and routing problems. Because of the humanitarian nature of the problem, the main objective is to maximize the utility of the assignment of the donated items. There are several criteria regarding donations and recipients that affect the utility of an assignment, such as the travel time between the location of the donation and the candidate recipient, income level, age, and the number of household of the candidate recipient, the recipient's previous usage of this service, and the age of donated item. Priorities among criteria are set by making a series of judgments based on pairwise comparisons as in the Analytical Hierarchy Process. We consider a real life problem for a district in Izmir, Turkey. The planning period is taken as a working day, and there are time windows in which donors and residents are willing to be served, i.e., the donor must be visited on a specified time interval during the working day. A single truck with a limited capacity is to distribute the donations. The output of the mathematical model is the optimal assignment of the items and the visiting sequence of individuals to maximize total utility. We present our model along with numerical examples and results. (C) 2012. The authors. Published by Elsevier Ltd. Selection and/or peer-review under responsibility of the Program