usually considered to be infeasible [9]. In other approaches, the times windows may be violated, leading to a tardy service at some customers [3].

Some problems introduce multiple depots as opposed to only a **single depot in the classical case.**
Along with this sometimes comes the additional decision of open routes, where vehicles do not return to the place they depart from but to some other depot. Also, different types of vehicles may be considered, leading to a heterogeneous fleet in terms of the abilities of the vehicles.

Unfortunately, most problems of this domain are N P**-hard. As a result, heuristics and more recently**
metaheuristics have been developed with increasing success [5]. In order to improve known results, more and more refined techniques have been proposed that are able to solve, or at least approximate very closely, a large number of established benchmark instances. With the increasing specialization of techniques goes however a decrease in generality of the resolution approaches. While the optimality criterion of minimizing the total traveled distances is the most common, more recent approaches recognize the vehicle routing problem as a multi-objective optimization problem [4, 6–8]. Here, the overall problem lies in identifying a Pareto-optimal solution x
∗
**that**
is most preferred by a decision maker. As the relevant objective functions are often of conflicting nature, a whole set of potential Pareto-optimal solutions exists among which this choice has to be made. In the current article, a framework for interactive multi-objective vehicle routing is presented that aims to address two critical issues: (i) the necessary generality of resolution approaches when trying to solve a range of problems of different characteristics, and **(ii) the integration of multiple objectives**
in the resolution process.

## 2 A Framework For Interactive Multi-Objective Vehicle Routing

Independent from the precise characteristics of the particular VRP, two types of decisions have to be made when solving the problem.

1. Assignment of customers to vehicles (clustering).

2. Construction of a route for a given set of customers (sequencing).
It is well-known that both types of decisions influence each other to a considerable extent. The here presented framework therefore proposes the use of a set **of elements to handle this issue with** upmost generality. Figure 1 gives an overview about the elements used.

- The marketplace **represents the element where orders are offered for transportation.**
- Vehicle agents **place bids for orders on the marketplace. These bids take into consideration**
the current routes of the vehicles and the potential change when integrating an additional order.

- An ontology **describes the precise properties of the vehicles such as their capacity, availability,**
current location, etc. This easily allows the consideration of different types of vehicles.