In this article, the Heterogeneous Vehicle Routing Problem with Multiple Deliverymen and Simultaneous Pickup and Delivery (HVRPMDSPD) is discussed. This problem is inspired by real world reverse logistics applications where a bottling company, using a fleet of different vehicles, must deliver beverages to clients and also pick up empty cases of bottles to recycle. Moreover, it is usually not possible to stop at every client’s location, and many clients might be close to one another. This proximity allows the vehicles to park at certain areas from where the deliverymen can serve the clients nearby on foot. Employing more deliverymen on a given route cuts down service times, but also potentially raises operational costs. The HVRPMDSPD is modelled mathematically as a Mixed Integer Linear Programming Model (MILP) problem. A constructive heuristic was developed so as to provide an initial solution for the solver CPLEX, and the solutions obtained were investigated.