The paper deals with a complex transportation problem with an immediate practical application. A deterministic model is considered. The vehicle has to perform a route through the city to fulfil set of delivery demands having defined time windows to make service. We would like to find the route with minimal cost measured by weighted sum of earliness/tardiness penalties caused by violation of determined time windows. This problem is equivalent to the scheduling problem with earliness and tardiness penalties known already in the literature. As the added value of this paper, we provide some new theoretical properties based on so called block approach. Using these properties we devise a efficient metaheuristic algorithm to solve the problem. Paper provides components of the algorithm as well as results of computer test. Numerical tests confirm better algorithm quality evaluation comparing to other known so far approaches. The problem can be extended on the fleet of vehicles with limited capacities and pickup and/or delivery demands.
展开▼
