A vehicle assignment problem (VAP) in a road, long-haul, passenger transportation company with heterogeneous fleet of buses is considered in the paper. The mathematical model of the VAP is formulated in terms of rnultiobjective, combinatorial optimization. It has a strategic, long-term character and takes into account four criteria that represent interests of both passengers and the company's management. The decision consists in the definition of weekly operating frequency (number of rides per week) of buses on international routes between Polish and Western European cities. The VAP is solved in a step-wise procedure. In the first step a sample of efficient (Pareto-optimal) solutions is generated using an original metaheuristic method called Pareto Memetic Algorithm (PMA). In the second step this sample is reviewed and evaluated by the Decision Maker (DM). In this phase an interactive, multiple criteria analysis method with graphical facilities, called Light Beam Search (LBS), is applied. The method helps the DM to define his/her preferences, direct the search process and select the most satisfactory solution.