Pickup-and-Delivery Problems (PDPs) constitute an important family of routing problems in which goods or passengers have to be transported from different origins to different destinations. These problems are usually defined on a graph in which vertices represent origins or destinations for the different entities (or commodities) to be transported. PDPs can be classified into three main categories according to the type of demand and route structure being considered. In many-to-many (M-M) problems, each commodity may have multiple origins and destinations and any location may be the origin or destination of multiple commodities. These problems arise, for example, in the repositioning of inventory between retail stores or in the management of bicycle or car sharing systems. One-tomany- to-one (1-M-1) problems are characterized by the presence of some commodities to be delivered from a depot to many customers and of other commodities to be collected at the customers and transported back to the depot. These have applications, for example, in the distribution of beverages and the collection of empty cans and bottles. They also arise in forward and reverse logistics systems where, in addition to delivering new products, one must plan the collection of used, defective, or obsolete products. Finally, in one-to-one (1-1) problems, each commodity has a single origin and a single destination between which it must be transported. Typical applications of these problems are less than- truckload transportation and urban courier operations.